[数组双指针] 0167. 两数之和 II - 输入有序数组

1. 题目链接

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

2. 题目大意

描述：给定一个下标从 1 开始计数、升序排列的整数数组：numbers 和一个目标值 target。

要求：从数组中找出满足相加之和等于 target的两个数，并返回两个数在数组中下的标值。

说明：

• 2≤numbers.length≤3×104。
• −1000≤numbers[i]≤1000。
• numbers 按非递减顺序排列。
• −1000≤target≤1000。
• 仅存在一个有效答案。

3. 示例

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9。因此 index1 = 1, index2 = 2。返回 [1, 2]。

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6。因此 index1 = 1, index2 = 3。返回 [1, 3]。

4. 解题思路

1. 思路1: 对撞指针

可以考虑使用对撞指针来减少时间复杂度。具体做法如下：

1. 使用两个指针 left，right。left 指向数组第一个值最小的元素位置，right 指向数组值最大元素位置。
2. 判断两个位置上的元素的和与目标值的关系。
   1. 如果元素和等于目标值，则返回两个元素位置。
   2. 如果元素和大于目标值，则让 right 左移，继续检测。
   3. 如果元素和小于目标值，则让 left 右移，继续检测。
3. 直到 left 和 right 移动到相同位置停止检测。
4. 如果最终仍没找到，则返回 [−1,−1]。

2 思路2: 双指针

利用 HashMap 可以通过遍历数组找到数字组合，时间和空间复杂度均为 O(N) 。

注意本题的 numbers 是 排序数组 ，因此可使用 双指针法 将空间复杂度降低至 O(1) 。

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

循环搜索： 当双指针相遇时跳出。

计算和 s=numbers[i]+numbers[j] 。

若 s>target ，则指针 j 向左移动，即执行 j=j−1 。

若 s<target ，则指针 i 向右移动，即执行 i=i+1 。

若 s=target ，由于题目要求索引从 1 开始，因此返回数组 [i+1,j+1] 。

若循环结束，则返回空数组，代表无和为 target 的数字组合。

5. 参考代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0; 
        int right = numbers.length-1;

        while(left < right){
            int total = numbers[left] + numbers[right];
            if(total == target){
                return new int[]{left+1, right+1};
            }else if(total < target){
                left++;
            }else{
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int s = numbers[i] + numbers[j];
            if (s < target) i++;
            else if (s > target) j--;
            else return new int[] { i + 1, j + 1 };
        }
        return new int[0];
    }
}