双指针

对撞双指针

力扣Offer57题

条件：nums是排序数组，因此可以使用双指针法将空间复杂度降低至O(1).

算法流程

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

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的数组组合

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