Two Sum II: Sorted Input
你会得到一个按非递减顺序排列的整数数组 numbers，以及一个整数 target。恰好有一对不同位置上的值相加等于 target。返回这两个位置的从 0 开始的索引，较小的索引在前。
函数
- numbersinteger-array
- 排序后的整数数组
- targetinteger
- 两个值的和必须达到
- 返回值integer-array
- 两个从 0 开始的索引 [i, j]，其中 i < j 且 numbers[i] + numbers[j] == target
约束条件
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbers按非递减顺序排列。- 恰好有一对索引
i < j满足numbers[i] + numbers[j] == target。
示例
- 输入
- numbers = [-4, 1, 3, 8, 12]target = 9
- 输出
- [1, 3]
- 解释
- 1 位于索引 1，8 位于索引 3，而且 1 + 8 = 9。没有其他数对的和是 9：例如，-4 + 12 = 8。
- 输入
- numbers = [2, 2, 5, 7]target = 4
- 输出
- [0, 1]
- 解释
- 索引 0 和 1 处的两个 2 是两个不同的位置，因此它们可以组成一对：2 + 2 = 4。
- 输入
- numbers = [-10, -3, 0, 6]target = -4
- 输出
- [0, 3]
- 解释
- 索引 0 处的 -10 和索引 3 处的 6 相加，得到 -10 + 6 = -4。答案可以跨越整个数组。
进阶
你能否用 O(n) 的时间和 O(1) 的额外内存解决这个问题？
提示
逐个打开提示，每个都会多透露一点。
数组已经排序。一起看看最小值和最大值。当它们的和小于
target时，这说明了什么？如果第一个值加上最后一个值太小，那么第一个值与任何其他值配对都太小，因为最后一个值已经是最大的了。你可以排除它。
在两端各保留一个指针。总和太小时，将左指针向右移动；总和太大时，将右指针向左移动。当总和等于
target时停止。
题解
数组已经排序，顺序会告诉你该往哪个方向移动。在两端各放置一个指针。如果总和太小，只有更大的左侧值才能解决问题；如果总和太大，只有更小的右侧值才能解决问题。每一步都会永久排除一个值，因此只需遍历一次，就能找到这对值，而且不需要额外的内存。
检查每一对
结果正确，但无法在最大的测试中运行完毕
思路
尝试每一对位置 i < j，并检查 numbers[i] + numbers[j] 是否等于 target。由于 j 从 i 后一位开始，所以找到的数对中，较小的索引在前。
这种方法忽略了排序顺序。当 n = 10^4 时，约有 5 × 10^7 对，而答案如果接近数组末尾，就意味着几乎要检查所有数对。
算法
- 遍历每个索引，让
i依次取值。 - 让
j从i+1开始遍历，直到最后一个索引。 - 如果
numbers[i] + numbers[j]等于target，返回[i, j]。
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []为每个伙伴进行二分查找
思路
确定 numbers[i] 后，它的搭档恰好是 target - numbers[i]。i 右侧的范围已排序，因此二分查找可以在 O(log n) 步内判断搭档是否在其中。只在右侧查找，可以确保较小的索引在前，并避免一个值与自身配对。由于配对是唯一的，找到的任何匹配项都是答案。
在第一个示例中，i = 0 需要 13，但找不到；i = 1 需要 8，在索引 3 处找到。这相当于进行 n 次查找，每次查找需要 O(log n) 步。
算法
- 让
i从 0 循环到n-2。 - 计算
need = target - numbers[i]。 - 在索引
i+1到n-1的范围内对need进行二分查找。 - 如果在
mid处找到它，就返回[i, mid]。
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []从两端开始的双指针
思路
看看 numbers[left] + numbers[right]。如果它太小，numbers[left] 就不可能是答案的一部分：即使与当前仍在考虑范围内的最大值配对，结果也不够大。如果它太大，numbers[right] 即使与剩下的最小值配对，结果也会超出目标值。因此，每次移动都会丢弃一个不可能出现在配对中的值，而不会丢弃配对本身。指针最多移动 n-1 次就能找到答案，只需要两个变量。
对于 [-4, 1, 3, 8, 12]，当 target = 9 时：-4 + 12 = 8，结果太小，所以 left 移动到索引 1。接着，1 + 12 = 13，结果太大，所以 right 移动到索引 3。现在 1 + 8 = 9，答案是 [1, 3]。
算法
- 将
left设为 0，将right设为n-1。 - 当
left < right时，计算total = numbers[left] + numbers[right]。 - 如果
total等于target，则返回[left, right]。 - 如果
total较小，就将left加 1；如果较大，就将right减 1。
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
易错点和边界情况
- 返回从 1 开始的位置。对于
[-4, 1, 3, 8, 12]和target = 9，答案是[1, 3]，不是[2, 4]。在 Lua 和 R 中，返回前减去 1。 - 使用
left <= right进行循环。当两个指针相遇时，求和会把同一个值计算两次。 - 移动了错误的指针。总和太小，就需要更大的值，而只有
left能提供更大的值。 - 拒绝重复值。对于
[2, 2, 5, 7]和target = 4，要使用两个 2，它们位于不同的位置。
常见问题3
Two Sum II 的时间复杂度是多少？
双指针解法的时间复杂度为 O(n)，额外空间复杂度为 O(1)：每一步都会将一个指针向内移动，它们最多经过 n-1 步就会相遇。对每个配对元素进行二分查找需要 O(n log n)，检查所有配对则需要 O(n²)。
为什么不使用像第一道 Two Sum 那样的哈希表？
哈希表也能解决这个问题，时间复杂度也是 O(n)，但它最多会存储 n 个值。有序排列让这部分内存变得不必要：仅凭总和，两个指针就能确定移动方向。面试官会问这个版本，看看你是否利用了给定的顺序。
在这里，什么时候二分查找是更好的选择？
当一个值固定，而你只需要找到与它配对的值时。如果必须让 numbers[0] 出现在这一对中，一次二分查找就能在 O(log n) 时间内找到另一个索引。要查找一对未知的值，双指针扫描比进行 n 次单独查找更快。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def twoSumSorted(numbers, target):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
numbers = [-4, 1, 3, 8, 12] target = 9
预期输出
[1, 3]