LeetCode LCR 006. 两数之和 II - 输入有序数组
题目描述
题意分析
在已经非递减排序的数组
numbers中，找到两个不同位置，使对应元素之和等于target，返回这两个位置的下标。题目保证恰好有一个有效答案。本题下标从零开始，结果满足前一个下标小于后一个下标；这与主站第 167 题的一基下标不同。相同数值可以出现在不同位置，但不能重复使用同一位置，也不需要再次排序。
解法：有序数组两端双指针
核心思路
[!blue]
用
left、right指向当前候选区间的两端，先比较这两个数的和。排序保证左端是当前最小候选，右端是当前最大候选，所以每次比较都能排除一个不可能参与答案的端点。若和小于目标，左端即使配上当前最大的右端也不够，改配区间内更小的数只会更小，因此可以排除当前左端，让
left右移。若和大于目标，右端即使配上当前最小的左端也过大，配上更大的数更不可能满足，因此让right左移。已排除的端点都不可能与剩余候选形成答案，所以唯一答案始终留在尚未排除的区间中。两指针严格保持不同位置；和等于目标时，直接返回当前零基下标即可。
每轮至少移走一个端点，候选区间持续缩小，不需要额外哈希表。代码保留宽整数求和，且整个过程中不修改输入数组或下标对应关系。
解题步骤
- 初始化
left = 0、right = numbers.length - 1。- 在
left < right时计算两端和。- 和等于目标则返回两个当前下标；偏小就右移左端，偏大就左移右端。
- 题目保证有解，合法输入会在两指针相遇前找到答案。
代码实现
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
long sum = (long) numbers[left] + numbers[right];
if (sum == target) {
return new int[] {
left,
right
};
}
if (sum < target) {
left++;
} else {
right--;
}
}
return new int[0];
}
}
func twoSum(numbers []int, target int) []int {
left, right := 0, len(numbers)-1
for left < right {
sum := int64(numbers[left]) + int64(numbers[right])
if sum == int64(target) {
return []int{
left,
right,
}
}
if sum < int64(target) {
left++
} else {
right--
}
}
return []int{}
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(n)$，两个指针合计最多移动线性次数。
- 辅助空间复杂度：$O(1)$，只使用端点和求和变量，返回结果长度固定为二。
关键点总结
[!green]
- 移动端点基于“与剩余最有利对手仍无法满足”的排除论证。
- 输入有序，因此能同时维持候选区间和原始位置对应关系。
- 返回零基下标，并用
left < right保证不同位置。
易错点总结
[!yellow]
- 本题下标不用加一，不能直接复制主站第 167 题的返回格式。
- 和偏小时应增大左侧候选，偏大时应减小右侧候选，移动方向不能颠倒。
- 两指针相同会复用一个元素，循环不能使用
left <= right。- 重复数值并不代表重复位置，不能先去重。
- 数组已经有序，不必重新排序或额外改变原下标。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1. 两数之和 | 简单 | 原题无序，需要哈希查互补值；本题有序，可以用两端指针线性收缩。 |
| 15. 三数之和 | 中等 | 先固定一个值后，剩余部分同样转化为有序两数之和，并增加结果去重。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！