图解LeetCode——剑指 Offer 57. 和为s的两个数字

一、题目

输入一个递增排序的数组和一个数字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^)/ ~ 「干货分享，每天更新」