167. 两数之和 II - 输入有序数组

题目

给你一个下标从 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 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

解答

思路

暴力做法就是两重循环 $O(n^2)\approx {10}^9$ 会超时。

auto& nums = numbers;
for (int i = 0; i < nums.size() - 1; i ++) {
    for (int j = 1; j < nums.size(); j ++) {
        if (nums[i] + nums[j] == target) {
            return {i, j};
        }
    }
}

考虑到这是一个 非递减数组，因此我们可以使用 双指针 方法，用 i, j 分别指向第一个数和最后一个数，也就是数组中的 最小的数和最大的数，它们俩相加，和为 sum：

• 如果 sum > target，此时如果将小的数向右移动变大，那么结果反而会更大，因此只能移动 大的数向左，才有可能使得 sum == target
• 如果 sum < target，同理，只能移动小的数向右，使得 sum 变大
• 每次相当于都取 剩下的数中最小的数和最大的数

有点循环不变式的意思了。

相当于每次花费 $O(1)$ 的时间排除一个数。注意，这也是 相向双指针 的精髓：每次通过 check() 函数可以将其中某个指针向内侧移动，从而排除一个数（这个数和数组中的任何一个数相加都不可能等于 target，因此获取的信息效率是 $n$）。因此：

• 时间复杂度为 $O(n)$
• 空间复杂度为 $O(1)$

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0;
        int r = numbers.size() - 1;

        while (l < r) {
            if (numbers[l] + numbers[r] == target) {
                return {l + 1, r + 1};
            }
            else if (numbers[l] + numbers[r] > target) {
                r --;
            }
            else {
                l ++;
            }
        }

        return {};
    }
};

写代码是注意题干中的下标从 1 开始而不是从 0 开始。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        
        while True: # left < right
            s = numbers[left] + numbers[right]
            
            if s == target:
                break
            if s > target:
                right -= 1
            else:
                left += 1

        return [left + 1, right + 1]

语法知识总结：

• {i, j} 是 C++11 引入的语法糖：列表初始化
• len(numbers) 是 Python 中返回 [] 长度的函数