LeetCode 剑指 Offer 57. 和为s的两个数字
题目描述
题意分析
在递增排序的数组中选择两个不同位置，使对应数值之和等于
target。返回两个数值而非下标；有多组答案时，任意一组即可。
解法：双指针收缩边界
核心思路
[!blue]
用
left、right指向尚未排除区间的两端，比较nums[left] + nums[right]与目标。数组有序，因此每次比较都能排除一个端点，而不只是排除当前这一对数。若和偏小，左端与当前最大值相加都不够，改配区间内其他数只会更小，所以任何答案都不可能再使用这个左端，令
left++。若和偏大，右端与当前最小值相加都太大，改配其他数只会更大，所以可以令right--。已排除的端点都不可能参与剩余答案，合法数对始终留在两指针之间。和相等时直接返回；当两指针相遇，已没有两个不同位置可选，代码返回空数组。
解题步骤
- 初始化
left = 0、right = nums.length - 1。- 当
left < right时，计算两个端点的和sum。sum == target时返回两端数值；sum < target时右移左指针，否则左移右指针。- 循环结束仍未找到时返回空数组。
代码实现
class Solution {
public int[] twoSum(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[] {
nums[left],
nums[right]
};
}
if (sum < target) {
// 与当前最大值相加仍偏小，左端不可能属于答案。
left++;
} else {
// 与当前最小值相加仍偏大，右端不可能属于答案。
right--;
}
}
return new int[0];
}
}
func twoSum(nums []int, target int) []int {
left, right := 0, len(nums)-1
for left < right {
sum := nums[left] + nums[right]
if sum == target {
return []int{
nums[left],
nums[right],
}
}
if sum < target {
// 与当前最大值相加仍偏小，左端不可能属于答案。
left++
} else {
// 与当前最小值相加仍偏大，右端不可能属于答案。
right--
}
}
return []int{}
}
复杂度分析
- 时间复杂度：$O(n)$，其中
n为数组长度；每次循环使两指针的距离缩短 1，最多移动n - 1次。- 空间复杂度：$O(1)$，只使用两个指针和当前和。
关键点总结
[!green]
- 有序性支持一次比较排除整个端点。
- 相等数值可以来自不同位置，不能复用同一个下标。
易错点总结
[!yellow]
- 和偏小时移动右指针，会使候选和更小并漏掉解。
- 一次移动两端，没有分别排除两者的依据。
- 返回指针下标而不是两数值，不符合本题要求。
- 循环条件不能写成
left <= right，否则可能把同一个位置使用两次。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1. 两数之和 | 简单 | 原题无序，需要哈希查互补值；本题有序，可以用两端指针线性收缩。 |
| 15. 三数之和 | 中等 | 先固定一个值后，剩余部分同样转化为有序两数之和，并增加结果去重。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！