《剑指 Offer》专项突破版 - 面试题 6 : 排序数组中的两个数字之和（C++ 实现的四种方法）

---

前言

题目链接：LCR 006. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

题目：

输入一个递增排序的数组和一个值 k，请问如何在数组中找出两个和为 k 的数字并返回它们的下标？假设数组中只存在一对符合条件的数字，同时一个数字不能使用两次。例如，输入数组 [1, 2, 4, 6, 10]，k 的值为 8，数组中的数字 2 与 6 的和为 8，它们的下标分别为 1 与 3。

---

一、暴力求解

在面试的时候很多人都能想到这个问题最直观的解法，就是先在数组中固定一个数字，再依次判断数组中其余数字与它的和是不是等于 k。如果数组的长度是 n，则这种解法的时间复杂度是 O(n^2)。

class Solution {
public:
 ? ?vector<int> twoSum(vector<int>& numbers, int target) {
 ? ? ? ?int n = numbers.size();
 ? ? ? ?for (int i = 0; i < n - 1; ++i)
 ? ? ?  {
 ? ? ? ? ? ?for (int j = i + 1; j < n; ++j)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?if (numbers[i] + numbers[j] == target)
 ? ? ? ? ? ? ? ? ? ?return { i, j };
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return { };
 ?  }
};

---

二、二分查找

方法一可以用二分查找来优化。假设扫描到数字 i，如果数组中存在另一个数字 k - i，那么就找到了一对和为 k 的数字。我们没有必要通过从头到尾逐个扫描数组中的每一个数字来判断数组中是否存在 k - i，由于数组是递增排序的，因此可以用二分查找在数组中搜索 k - i。二分查找的时间复杂度是 O(logn)，因此优化之后的解法的时间复杂度是 O(nlogn)。

class Solution {
public:
 ? ?vector<int> twoSum(vector<int>& numbers, int target) {
 ? ? ? ?int n = numbers.size();
 ? ? ? ?for (int i = 0; i < n - 1; ++i)
 ? ? ?  {
 ? ? ? ? ? ?int left = i + 1;
 ? ? ? ? ? ?int right = n - 1;
 ? ? ? ? ? ?int diff = target - numbers[i];
 ? ? ? ? ? ?while (left <= right)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?int mid = (left + right) / 2;
 ? ? ? ? ? ? ? ?if (numbers[mid] < diff)
 ? ? ? ? ? ? ? ? ? ?left = mid + 1;
 ? ? ? ? ? ? ? ?else if (numbers[mid] > diff)
 ? ? ? ? ? ? ? ? ? ?right = mid - 1;
 ? ? ? ? ? ? ? ?else
 ? ? ? ? ? ? ? ? ? ?return { i, mid };
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return { };
 ?  }
};

---

三、哈希表

上述解法还可以用空间换时间进行优化。可以先将数组中的所有数字都放入一个哈希表，然后逐一扫描数组中的每个数字。假设扫描到数字 i，如果哈希表中存在另一个数字 k - i，那么就找到了一对和为 k 的数字。判断哈希表中是否存在一个数字的时间复杂度是 O(1)，因此新解法的时间复杂度是 O(n)，空间复杂度也是 O(n)。

class Solution {
public:
 ? ?vector<int> twoSum(vector<int>& numbers, int target) {
 ? ? ? ?unordered_map<int, int> ht; ?// key 为数字，value 为数字的下标
 ? ? ? ?int n = numbers.size();
 ? ? ? ?for (int i = 0; i < n; ++i)
 ? ? ?  {
 ? ? ? ? ? ?if (ht.count(target - numbers[i]))
 ? ? ? ? ? ? ? ?return { ht[target - numbers[i]], i };
?
 ? ? ? ? ? ?ht[numbers[i]] = i;
 ? ? ?  }
 ? ? ? ?return { };
 ?  }
};

---

四、相向双指针

存在时间复杂度是 O(n)、空间复杂度是 O(1) 的解法。我们用两个指针 left 和 right 分别指向数组中的两个数字。指针 left 初始时指向数组的第 1 个（下标为 0）数字，指针 right 初始时指向数组的最后一个数字。

1. 如果指针 left 和 right 指向的两个数字之和等于输入的 k，那么就找到了符合条件的两个数字。

2. 如果指针 left 和 right 指向的两个数字之和小于 k，那么我们希望两个数字的和再大一点。由于数组已经排好序，因此可以考虑把指针 left 向右移。因为在排序数组中右边的数字要大一些，所以两个数字的和也要大一些，这样就有可能等于输入的数字 k。

3. 同样，当两个数字的和大于输入的数字 k 时，可以把指针 right 向左移动，因为在排序数组中左边的数字要小一些。

class Solution {
public:
 ? ?vector<int> twoSum(vector<int>& numbers, int target) {
 ? ? ? ?int left = 0;
 ? ? ? ?int right = numbers.size() - 1;
 ? ? ? ?while (left < right)
 ? ? ?  {
 ? ? ? ? ? ?int sum = numbers[left] + numbers[right];
 ? ? ? ? ? ?if (sum < target)
 ? ? ? ? ? ? ? ?++left;
 ? ? ? ? ? ?else if (sum > target)
 ? ? ? ? ? ? ? ?--right;
 ? ? ? ? ? ?else
 ? ? ? ? ? ? ? ?return { left, right };
 ? ? ?  }
 ? ? ? ?return { };
 ?  }
};