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

分析

这道题算不上特别难。 基本上一眼就能得出双指针的方法。 但在介绍双指针方法之前，先来看一看以二分的思路是如何完成的。

二分的思路是先固定一个数字， 然后在右侧二分寻找满足 numbers[left] + numbers[right] == target 的 right。 换句话说，在固定好一个数字 numbers[i] 后，我们需要寻找一个满足target - numbers[i] 的 numbers[mid]。 由于答案唯一，所以我们在找到后可以直接返回。 注意：这道题在计算中间值 mid 时，由于编译器优化的特性可以考虑用 >>1 来替代 /2，从而方便编译器优化。

而双指针法则更简单。 我们只需要两个指针 left 和 right。 在 numbers[left] + numbers[right] = target 之前对 left 和 right 进行向中间移动即可。

解答

1
class Solution {
2
public:
3
  vector<int> twoSum(vector<int> &numbers, int target) {
4
    int left = 0, right = numbers.size() - 1;
5

6
    while (left < right) {
7
      auto sum = numbers[left] + numbers[right];
8

9
      if (sum == target)
10
        return {left + 1, right + 1};
11
      else if (sum > target)
12
        right--;
13
      else
14
        left++;
15
    }
16

17
    return {-1, -1};
18
  }
19
};