剑指 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]

解题思路:

利用HashMap可以通过遍历数组找到数字组合,时间和空间复杂度均为O(N) ;
注意本题的nums是排序数组，因此可使用双指针法将空间复杂度降低至0(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,i)。

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

代码

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