输入一个递增排序的数组和一个数字s
,在数组中查找两个数,使得它们的和正好是s
。如果有多对数字的和等于s
,则输出任意一对即可。
【输入】nums = [2,7,11,15], target = 9 【输出】[2,7] 或者 [7,2]
【输入】nums = [10,26,30,31,47,60], target = 40 【输出】[10,30] 或者 [30,10]
1
<= nums.length <= 10^5
1
<= nums[i] <= 10^6
根据题目描述,我们要寻找这个数组中两个数相加等于s
的任意一对数字。这里的一个关键点是数组本身就是递增的,那么这个我们就可以通过寻找一些规律来巧妙的解答这道题。那么规律到底是什么呢?我们来仔细分析一下。
通过上面的图,我们可以看出一个规律:
【head指针】当
head
指针向右移动时,nums[head]
值会越来越大; 【tail指针】当tail
指针向左移动时,nums[tail]
值会越来越小;
那么我们就可以创建双指针head
和tail
,然后总和(sum
)就是 nums[head] + nums[tail] ,可以与s
进行对比,来决定head指针或tail指针的移动方式:
【如果sum<s】则需要
sum
值更大,那么就需要head
指针向右移动; 【如果sum>s】则需要sum
值更小,那么就需要tail
指针向左移动; 【如果sum==s】则表示找到了目标的两个数,那么最终结果就是nums[head]
和nums[tail]
这两个数。
为了更便于理解,我们还是举例,假设nums=[2, 7, 11, 15, 19]
,target=18
。那么具体的处理逻辑请见下图所示:
class Solution {
public int[] twoSum(int[] nums, int target) {
int head = 0, tail = nums.length - 1;
while(head < tail) {
int sum = nums[head] + nums[tail];
if (sum == target) return new int[]{nums[head], nums[tail]};
if (sum < target) head++;
else tail--;
}
return new int[2];
}
}