两数之和[中等]

一、题目

给你一个下标从1开始的整数数组numbers，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数target的两个数。如果设这两个数分别是numbers[index1]和numbers[index2]，则1 <= index1 < index2 <= numbers.length。以长度为2的整数数组[index1, index2]的形式返回这两个整数的下标index1和index2。你可以假设每个输入 只对应唯一的答案 ，而且你不可以重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。

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

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

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

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers按非递减顺序排列
-1000 <= target <= 1000
仅存在一个有效答案

二、代码

【1】使用二分查找法： 通过target - numbers[i]得到目标值，然后根据二分查找目标值，二分查找小于目标值，取右边进行递归，否则取左边的数据进行递归。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // 通过 target - numbers[i] 得到目标值，然后根据二分查找目标值，二分查找小于目标值，取右边进行递归，否则取左边的数据进行递归。
        int left = 0, right = 0, val = 0, mid = 0;
        for (int i = 0; i < numbers.length; i++) {
            left = i + 1;
            right = numbers.length - 1;
            // 需要查找的值
            val = target - numbers[i];
            // 中间数据
            while(left <= right) {
                mid = (right - left) / 2 + left;
                // 循环退出条件
                if (numbers[mid] == val) {
                    return new int[] {i + 1 , mid + 1};
                }
                // 如果中间值大于目标值，二分查找左边数组，否则查找右边数组
                if (numbers[mid] > val) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
        }
        return new int[]{-1,-1};
    }
}

时间复杂度： O(nlog⁡n)其中n是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是O(n)，寻找第二个数使用二分查找，时间复杂度是O(log⁡n)，因此总时间复杂度是O(nlog⁡n)。
空间复杂度： O(1)

【2】双指针： 初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // 思想：将左右指针累加后，如果sum > target 右指针-1，sum < target 左指针 + 1
        int left = 0 , right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1 , right + 1};
            } else if (sum > target){
                --right;
            }else {
                ++left;
            }
        }
        return new int[]{-1,-1};
    }
}

时间复杂度： O(n)其中n是数组的长度。两个指针移动的总次数最多为n次。
空间复杂度： O(1)

【3】O(n)的双指针解法的本质原理： 很多人做这个题目想不到正确的O(n)解法，即使看了答案理解了，下次再做的时候还是会忘记。要想真正理解这道题，就要明白解法背后的道理。这样不仅可以记住这道题，还能举一反三解决类似的题目。

很多题解只给出了双指针解法的代码，但没有说明解法的正确性。为什么双指针往中间移动时，不会漏掉某些情况呢？要解答这个问题，我们要从 缩减搜索空间 的角度思考这个解法。下面我将以文字和图片两种方式进行讲解。

首先放上参考答案：

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

需要注意的是，虽然本题叫做Two Sum II，但解法和Two Sum完全不同。

图解双指针解法的原理： 在这道题中，我们要寻找的是符合条件的一对下标(i,j)，它们需要满足的约束条件是：
【1】i、j都是合法的下标，即0≤i<n,0≤j<n；
【2】i<j（题目要求）；
而我们希望从中找到满足A[i] + A[j] == target的下标(i,j)。以n=8为例，这时候全部的搜索空间是：

由于i、j的约束条件的限制，搜索空间是白色的倒三角部分。可以看到，搜索空间的大小是O(n^2)数量级的。如果用暴力解法求解，一次只检查一个单元格，那么时间复杂度一定是O(n^2)。要想得到O(n)的解法，我们就需要能够一次排除多个单元格。那么我们来看看，本题的双指针解法是如何削减搜索空间的：

一开始，我们检查右上方单元格(0,7)，即计算A[0] + A[7]，与target进行比较。如果不相等的话，则要么大于target，要么小于target。

假设此时A[0] + A[7]小于target。这时候，我们应该去找和更大的两个数。由于A[7]已经是最大的数了，其他的数跟A[0]相加，和只会更小。也就是说A[0] + A[6]、A[0] + A[5]、……、A[0] + A[1]也都小于target，这些都是不合要求的解，可以一次排除。这相当于i=0的情况全部被排除。对应用双指针解法的代码，就是i++，对应于搜索空间，就是削减了一行的搜索空间，如下图所示。

排除掉了搜索空间中的一行之后，我们再看剩余的搜索空间，仍然是倒三角形状。我们检查右上方的单元格(1,7)，计算A[1] + A[7]与target进行比较。

假设此时A[0] + A[7]大于target。这时候，我们应该去找 和更小的两个数。由于A[1]已经是当前搜索空间最小的数了，其他的数跟A[7]相加的话，和只会更大。也就是说A[1] + A[7]、A[2] + A[7]、……、A[6] + A[7]也都大于target，这些都是不合要求的解，可以一次排除。这相当于j=0的情况全部被排除。对应用双指针解法的代码，就是j++，对应于搜索空间，就是削减了一列的搜索空间，如下图所示。

可以看到，无论A[i] + A[j]的结果是大了还是小了，我们都可以排除掉一行或者一列的搜索空间。经过n步以后，就能排除所有的搜索空间，检查完所有的可能性。搜索空间的减小过程如下面动图所示：