图解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。那么具体的处理逻辑请见下图所示：

四、代码实现

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];
    }
}