一、题目
输入一个递增排序的数组和一个数字s
,在数组中查找两个数,使得它们的和正好是s
。如果有多对数字的和等于s
,则输出任意一对即可。
二、示例
2.1> 示例 1:
【输入】nums = [2,7,11,15], target = 9
【输出】[2,7] 或者 [7,2]
2.2> 示例 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];
}
}
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享,每天更新」
网友评论