27.两数之和 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 * 104
- -1000 <= numbers[i] <= 1000
- numbers 按 非递减顺序 排列
- -1000 <= target <= 1000
- 仅存在一个有效答案
思路
注意题目说仅存在一个有效答案
这道题的关键信息是数组已经有序，且要求 O(1) 空间。这两个条件直接指向双指针（对撞指针）解法。
为什么不用哈希表？
经典的「两数之和」（第 1 题）用哈希表，O(n) 时间但 O(n) 空间。本题明确要求 O(1) 空间，哈希表就不合适了。而本题数组有序，这是第 1 题没有的条件，正好能用双指针把空间降到 O(1)。
双指针（对撞指针）的核心思想
一个指针 left 放在最左（最小值），一个指针 right 放在最右（最大值），计算两者之和 sum:
- sum == target：找到了，直接返回。
- sum < target：和太小了，需要让和变大。因为数组有序，只能把 left 右移（换一个更大的数），right 左移只会让和更小。
- sum > target：和太大了，需要让和变小。只能把 right 左移（换一个更小的数）。
- 每一步都能排除一个数，所以是 O(n) 时间、O(1) 空间。
使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。
假设numbers[i]+numbers[j]=target是唯一解，其中0≤i<j≤numbers.length−1。
初始时两个指针分别指向下标0和下标numbers.length−1，左指针指向的下标小于或等于i，右指针指向的下标大于或等于 j。 除非初始时左指针和右指针已经位于下标 i 和 j，否则一定是左指针先到达下标 i 的位置或者右指针先到达下标 j 的位置。
-
如果左指针先到达下标 i 的位置，此时右指针还在下标 j 的右侧，
sum>target，因此一定是右指针左移，左指针不可能移到 i 的右侧。 -
如果右指针先到达下标 j 的位置，此时左指针还在下标 i 的左侧，
sum<target，因此一定是左指针右移，右指针不可能移到 j 的左侧。
由此可见，在整个移动过程中，左指针不可能移到 i 的右侧，右指针不可能移到 j 的左侧，因此不会把可能的解过滤掉。
由于题目确保有唯一的答案，因此使用双指针一定可以找到答案。
class Solution {
fun twoSum(numbers: IntArray, target: Int): IntArray {
// 左指针，指向较小值
var left = 0
// 右指针，指向较大值
var right = numbers.size - 1
while (left < right) {
val sum = numbers[left] + numbers[right]
when {
sum == target -> {
// 找到答案。题目要求下标从 1 开始，所以各 +1
return intArrayOf(left + 1, right + 1)
}
sum < target -> left++ // 和太小，左指针右移换更大的数
else -> right-- // 和太大，右指针左移换更小的数
}
}
// 题目保证有解，理论上不会走到这里；返回空数组兜底
return intArrayOf()
}
}
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers) - 1
result = [-1]*2
while left < right:
sum = numbers[left] + numbers[right]
if sum < target:
left += 1
elif sum > target:
right -= 1
else:
return [left+1, right+1]
return [-1, -1]
复杂度分析:
-
时间复杂度：O(n)，其中 n 是数组的长度。两个指针移动的总次数最多为 n 次。
-
空间复杂度：O(1)。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!