一、题目
输入一个递增排序的数组和一个数字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
。那么具体的处理逻辑请见下图所示:
四、代码实现
classSolution { publicint[] twoSum(int[] nums, inttarget) { inthead=0, tail=nums.length-1; while(head<tail) { intsum=nums[head] +nums[tail]; if (sum==target) returnnewint[]{nums[head], nums[tail]}; if (sum<target) head++; elsetail--; } returnnewint[2]; } }
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」