题目链接 ：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
image.png
题目解析
- 采用
HashMap
复杂度分析
空间复杂度: O(N)。
时间复杂度: O(N)。
- 由于本题是一个排序数组，可以采用双指针的方式进行探寻达到降低空间复杂度的目的。左右指针分别指向头尾，如果相加大于目标值就右指针往左移，如果相加小于目标值则左指针向右移。
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while(i < j) {
int s = nums[i] + nums[j];
if(s < target) i++;
else if(s > target) j--;
else return new int[] { nums[i], nums[j] };
}
return new int[0];
}
复杂度分析
空间复杂度: O(1)。
时间复杂度: O(N)。
网友评论