一、题目

剑指 Offer 57. 和为s的两个数字 难度简单

输入一个递增排序的数组和一个数字 s ，在数组中查找两个数，使得它们的和正好是 s 。如果有多对数字的和等于 s ，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,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 $

二、解法

2.1、对撞双指针法

核心思路

利用 HashMap 可以通过遍历数组找到数字组合，时间和空间复杂度均为 O(N) 。但本题的 $nums$ 是 排序数组 ，因此可使用 双指针法 将空间复杂度降低至 O(1) 。

算法流程：

1. 初始化： 双指针 $i , j$ 分别指向数组 $nums $的左右两端 （俗称对撞双指针）。

2. 循环搜索： 当双指针相遇时跳出；

   1. 计算和 $s = nums[i] + nums[j]$ ；
   2. 若 $s > target$ ，则指针 $j$ 向左移动，即执行 $j = j - 1$ ；
   3. 若 $s < target$ ，则指针 $i$ 向右移动，即执行 $i = i + 1$ ；
   4. 若 $s = target$ ，立即返回数组 $[ nums[i], nums[j] ]$ ；

3. 返回空数组，代表无和为 $target$ 的数字组合。

正确性证明：

记每个状态为 $S(i, j)$ ，即 $S(i, j) = nums[i] + nums[j]$ 。假设 $S(i, j) < target$ ，则执行 $i = i + 1$ ，即状态切换至 $S(i + 1, j)$ 。

• 状态 $S(i, j)$ 切换至 $S(i + 1, j)$ ，则会消去一行元素，相当于 消去了状态集合 ${S(i, i + 1), S(i, i + 2), …, S(i, j - 2), S(i, j - 1), S(i, j) }$ 。（由于双指针都是向中间收缩，因此这些状态之后不可能再遇到）。
• 由于 $nums$ 是排序数组，因此这些 消去的状态 都一定满足 $S(i, j) < target$ ，即这些状态都 不是解 。
• 结论： 以上分析已证明 “每次指针 $i$ 的移动操作，都不会导致解的丢失” ，即指针 $i$ 的移动操作是 安全的 ；同理，对于指针 $j$ 可得出同样推论；因此，此双指针法是正确的。

复杂度分析

时间复杂度：O(N)，N 为数组 $nums $ 的长度；双指针共同线性遍历整个数组。

空间复杂度：O(1)，变量 $i, j$ 使用常数大小的额外空间。

Code

因题目限定 $ 1 <= nums[i] <= 10^6 $ ，所以判断条件用相加后的结果不会溢出。如果两个操作数都是正整数，则使用$target - nums[i]$ 跟 $nums[j]$ 比较，这样保证不会溢出。因为 $nums[i]$ 可能是负数， $target - nums[i]$ 也可能越界，因此用 long 型去比可能是最安全的。

同样的例子还有二分查找，$(left + right) / 2$ 可以用 $left + ((rigth - left) » 1))$ 代替。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;

        while(i < j) {
            int s = nums[i] + nums[j];

            if(s < target) {
                i++;
            } else if(s > target) {
                j--;
            } else {
                return new int[] { nums[i], nums[j] };
            }
        }

        return new int[0];
    }
}

2.2、哈希表

核心思路

使用暴力枚举的时间复杂度较高的原因是寻找 $target - nums[i]$ 的时间复杂度过高。因此，使用哈希表可以将寻找 $target - nums[i]$ 的时间复杂度降低到从 O(N) 降低到 O(1)。

因本题的 $nums$ 是 排序数组 ，实际上使用 双指针法 可以将空间复杂度也降低至 O(1) ，但如果 $nums$ 是无序的，可以使用哈希表解法。

复杂度分析

时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个 $nums[i]$ ，我们可以 O(1) 地寻找 $target - nums[i]$ 。

空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 初始化哈希表
        Map<Integer, Integer> hashtable = new HashMap<>(nums.length);

        for (int i = 0; i < nums.length; ++i) {
            // 查询哈希表中是否存在 target - nums[i]
            if (hashtable.containsKey(target - nums[i])) {
                // 如果存在, 返回 [ target - nums[i], nums[i] ]
                return new int[]{hashtable.get(target - nums[i]), nums[i]};
            }

            // 将 nums[i] 插入到哈希表中，保证不会让 nums[i] 和自己匹配
            hashtable.put(nums[i], nums[i]);
        }

        // 没有找到符合条件的解, 返回 [ 0, 0 ]
        return new int[0];
    }
}

REF

https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/solution/mian-shi-ti-57-he-wei-s-de-liang-ge-shu-zi-shuang-/

https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/