LeetCode 167. 两数之和 II - 输入有序数组
题目描述
题意分析
在非递减排列的数组中，找到两个不同位置，使对应数值之和等于
target，返回两个位置从1开始的下标。数组允许重复值，只要使用的下标不同，就可以取两个相等的数。题目保证恰好存在一组答案，并要求常数额外空间。输入已经有序，不需要重新排序；返回的是位置而不是数值，而且同一个元素不能被使用两次。
解法：有序数组双指针
核心思路
[!blue]
用
left、right指向当前候选区间的两端。因为数组有序，左端是剩余最小值，右端是剩余最大值。比较这两个端点的和，关键不是随意让和变大或变小，而是判断哪一个端点已经不可能参与答案。若
numbers[left] + numbers[right] < target，左端即使配上当前最大的右端也不够。其他候选都不比右端大，因此这个左端与任何剩余位置相加都偏小，可以排除它，令left++。若两端之和大于目标，右端即使配上当前最小的左端也已经过大。其他候选都不比左端小，因此这个右端与任何剩余位置相加都偏大，可以排除它，令
right--。每轮只删除已经证明不可能属于答案的位置，所以答案始终保留在候选区间内。两个指针不断靠拢，最终遇到和等于目标的一对；循环使用
left < right，确保不会让同一个元素与自身配对。
解题步骤
- 初始化
left = 0、right = numbers.length - 1，候选区间覆盖整个数组。- 只要
left < right，计算两端之和。- 和等于目标时，返回
left + 1、right + 1，转换成题目规定的下标。- 和偏小时排除左端，和偏大时排除右端，继续比较。
- 题目保证有解，合法输入会在循环内返回；末尾返回空数组仅用于补全函数返回路径。
代码实现
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[] {
left + 1,
right + 1
};
} else if (sum < target) {
// 数组升序，左指针右移才能增大当前和。
left++;
} else {
right--;
}
}
return new int[0];
}
}
func twoSum(numbers []int, target int) []int {
left := 0
right := len(numbers) - 1
for left < right {
sum := numbers[left] + numbers[right]
if sum == target {
return []int{
left + 1,
right + 1,
}
} else if sum < target {
// 当前和偏小，只能移动左指针增大和。
left++
} else {
right--
}
}
return []int{}
}
复杂度分析
- 时间复杂度：$O(n)$。每轮至少有一个指针向内移动，最多移动
n - 1次。- 空间复杂度：$O(1)$。除返回结果外只使用常数个变量。
关键点总结
[!green]
- 有序性让每次比较都能排除整个端点对应的所有配对，而不只是跳过当前这一对。
- 保留的区间始终包含答案，指针只向内移动，不需要回退或额外记账。
- 位置不同由
left < right保证，数值重复不会影响判断。
易错点总结
[!yellow]
- 返回原下标会整体偏小一位，两个位置都要加
1。- 用
left <= right允许两指针重合，可能把同一个元素使用两次。- 和偏小时移动右端，只会让当前和更小，也没有排除左端之外位置的依据。
- 把相等数值当作重复答案而跳过，可能漏掉由两个不同位置上的相同数构成的唯一解。
- 另建哈希表会使用线性额外空间，不满足本题的空间要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1. 两数之和 | 简单 | 原题无序，需要哈希查互补值；本题有序，可以用两端指针线性收缩。 |
| 15. 三数之和 | 中等 | 先固定一个值后，剩余部分同样转化为有序两数之和，并增加结果去重。 |
| 170. 两数之和 III - 数据结构设计 | 简单 | 用哈希表查询当前元素所需的补值；本题利用有序性进一步改用双指针，该题把补值查询扩展为多次动态查询。 |
| 补充题 159. 有序数组中的目标和数对计数 | 中等 | 都用左右指针比较两端之和；补充题还要统计重复值形成的所有下标对。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！