LeetCode LCR 006. 两数之和 II - 输入有序数组
目录
题目描述
题意分析
给一个非递减排序的整数数组
numbers和一个目标值target，找出两个数使它们相加等于target，返回这两个数的下标（从 $0$ 开始）。题目保证有且仅有一组答案，且同一个元素不能重复使用。「有且仅有一组答案」这句保证很关键：它意味着搜索过程一旦命中就可以立刻返回，不需要继续找、也不需要处理「找不到」的分支；同时也保证了外层循环一定会在越界前终止。
「已排序」是全部算法信号的来源。数组无序时（对应 $1$ 题）只能靠哈希表把查找降到 $O(1)$；而一旦有序，就可以用「有序 + 目标值」的两大经典手段：一是二分查找定位配对值，二是相向双指针靠单调性收缩。本题的进阶要求还常常追加「只使用常量级额外空间」，这会把哈希表排除掉。
边界方面：元素可以是负数、可以有重复值，所以不能靠「值唯一」做任何假设；
target可能是任意整数，两数之和在极端数据下可能超出 32 位（本题范围内不会，但用减法target - numbers[i]而不是加法比较，本身就规避了这个风险）。另外「同一元素不可复用」要求配对的第二个下标必须严格大于第一个。
解法：二分查找判定答案
核心思路
暴力做法是双层循环枚举所有下标对，$O(n^2)$。瓶颈在内层：对固定的
i，我们其实是在问「数组里有没有值等于target - numbers[i]」，而这个问题被用线性扫描回答了——完全浪费了数组已经有序这个条件。观察：有序数组里的「查找某个值是否存在」正是二分查找的标准场景，可以从 $O(n)$ 降到 $O(\log n)$。于是固定第一个下标
i，令 $x = target - numbers[i]$，在区间 $[i+1, n-1]$ 内二分查找 $x$。搜索区间从i + 1而不是 $0$ 开始，一举解决了两件事：不会把同一个元素用两次，也不会把(i, j)和(j, i)重复枚举。二分部分用的是「找第一个大于等于 $x$ 的位置」这个下界写法，维持的不变量是：答案若存在，必定落在闭区间 $[l, r]$ 内；
r始终是一个「值大于等于 $x$」的候选或右端哨兵，l左侧的元素全部严格小于 $x$。循环条件写l < r，每轮把区间至少砍掉一半，退出时l == r，这个位置就是唯一的候选；再单独比一次numbers[l] == x才能确认 $x$ 真的存在，因为下界位置上的值可能大于 $x$。外层循环写成无终止条件的
for (int i = 0; ; ++i)，靠题目「必定有解」的保证退出。这在竞赛/面试里是可以接受的写法，但要能说清依据；如果题目不保证有解，就必须补上i < n - 1的边界。
解题步骤
- 外层枚举第一个下标
i，从 $0$ 递增。因为答案唯一，第一次命中即为答案，可以直接return。- 算出配对值
x = target - numbers[i]。用减法而不是「枚举j再判断和是否等于target」，是为了把问题变成一次纯粹的「查值」，从而能接上二分。- 二分区间取
[i + 1, n - 1]。左端从i + 1开始保证不复用同一元素；同时也让整体枚举不重不漏。- 循环条件
l < r，中点mid = (l + r) >> 1。这里l、r都是合法下标，和不超过 $2n$，不会溢出；用右移而非除法只是习惯，语义相同。numbers[mid] >= x时r = mid，否则l = mid + 1。收缩方式必须和「区间闭合」匹配：mid满足条件时它自己仍可能是答案，所以r收到mid（不能是mid - 1）；不满足时mid一定不是答案，l才能跳过它到mid + 1。这一对写法保证区间每轮严格变小，不会死循环。- 退出后必须再判一次
numbers[l] == x。下界查找只保证「l是第一个大于等于 $x$ 的位置」，并不保证等于；漏掉这一步会把「最接近但不相等」的元素当成答案。- 命中就返回
{i, l}；否则外层i前进一格，继续下一轮。以
numbers = [1, 2, 4, 6, 10]、target = 8走一遍，期望答案[1, 3]。i = 0：x = 8 - 1 = 7，在 $[1, 4]$ 上二分——mid = 2，numbers[2] = 4 < 7，l = 3；mid = 3，numbers[3] = 6 < 7，l = 4；此时l == r == 4退出，numbers[4] = 10 ≠ 7，未命中。i = 1：x = 8 - 2 = 6，在 $[2, 4]$ 上二分——mid = 3，numbers[3] = 6 >= 6，r = 3；mid = 2，numbers[2] = 4 < 6，l = 3；l == r == 3退出，numbers[3] = 6 == 6，命中，返回[1, 3]。注意i = 0那一轮里l最终停在了值为 $10$ 的位置——它确实是第一个「大于等于 $7$」的元素，但并不等于 $7$，正是那句额外的相等判断把它挡了下来。
代码实现
class Solution {
public int[] twoSum(int[] numbers, int target) {
// 题目保证必有一组解，所以外层不需要终止条件。
for (int i = 0, n = numbers.length;; ++i) {
int x = target - numbers[i];
// 在 [i + 1, n - 1] 上找第一个大于等于 x 的位置，区间左端保证不复用同一元素。
int l = i + 1, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (numbers[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
// 下界只保证「大于等于」，必须再确认一次相等。
if (numbers[l] == x) {
return new int[] {i, l};
}
}
}
}
func twoSum(numbers []int, target int) []int {
for i, n := 0, len(numbers); ; i++ {
x := target - numbers[i]
l, r := i+1, n-1
for l < r {
mid := (l + r) >> 1
if numbers[mid] >= x {
r = mid
} else {
l = mid + 1
}
}
if numbers[l] == x {
return []int{i, l}
}
}
}
复杂度分析
- 时间复杂度：$O(n \log n)$。外层最多枚举 $n$ 个起点，每次在长度不超过 $n$ 的有序区间上二分，代价 $O(\log n)$。凭的是有序性让「查找配对值」从线性扫描降到了折半。
- 空间复杂度：$O(1)$。只用了
i、x、l、r、mid几个下标变量，没有哈希表也没有额外数组，满足常量级空间的进阶要求。
关键点总结
- 「有序数组 + 找定值」是二分查找的标准触发条件；把「找一对数之和等于
target」改写成「对每个numbers[i]找target - numbers[i]」，是把配对问题降维成查找问题的通用手法。- 二分的收缩方式必须和区间语义严格配套：判定成立时
r = mid（保留候选），不成立时l = mid + 1（跳过），配l < r的循环条件，退出时区间恰好收成一个点。改动其中任何一处都要同步改其余两处。- 下界二分返回的是位置而不是答案，用完必须再验一次相等，这是
lower_bound类写法最容易漏的收尾。- 搜索区间从
i + 1而非 $0$ 起步，同时解决了「元素不可复用」和「配对不重复枚举」，比事后加if (j != i)判断更干净。- 面试视角：这道题面试官期待的最优解是相向双指针——
l从头、r从尾，和偏小就l++、偏大就r--，$O(n)$ 时间 $O(1)$ 空间，且能一句话说清正确性（当前和偏小时，l与任何更靠左的r配对只会更小，所以l位置的所有配对都可以整体排除）。二分版本是很好的过渡答案，它证明你能利用有序性，但被追问「还能更快吗」时必须立刻给出双指针，并解释为什么每次能安全地排除一整行/一整列。
易错点总结
- 错误写法：二分区间取
[0, n - 1]。输入numbers = [3, 3], target = 6时i = 0会找到l = 0，返回[0, 0]，同一个元素被用了两次。- 错误写法：判定成立时写
r = mid - 1。输入numbers = [1, 2, 4, 6, 10], target = 8时i = 1的二分会把numbers[3] = 6这个正确候选跳过，最终漏解并让外层一路i++越界。- 错误写法：判定不成立时写
l = mid。当l与r相邻时mid恒等于l，区间不再变小，直接死循环。- 错误写法：循环条件写
l <= r。退出时l会变成r + 1，可能等于n，紧接着的numbers[l]直接越界。- 错误写法：省掉退出后的
numbers[l] == x判断，直接返回{i, l}。输入numbers = [1, 2, 4, 6, 10], target = 8的i = 0轮会返回[0, 4]（$1 + 10 = 11$），完全错误。- 错误写法：把配对值算成
numbers[i] - target。输入numbers = [1, 2, 4, 6, 10], target = 8时i = 0要找 $-7$，永远找不到，外层递增到越界后抛异常。- 错误写法：外层不写终止条件却又用在「不保证有解」的变体题上。此题的无条件
for依赖题目保证；一旦题面改成「可能无解」，i会一路加到n并在numbers[i]处越界，必须补i < n - 1并在结尾返回空数组。- 错误写法：返回
{i + 1, l + 1}。这是 167 题的 1-based 约定，本题要求 0-based，直接答案错位。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 167. 两数之和 II - 输入有序数组 | 中等 | 与本题同题，但返回值是 1-based 下标，套用时要整体加一 |
| 剑指 Offer 57. 和为s的两个数字 | 简单 | 返回的是两个数值而非下标，双指针可直接输出元素 |
| 1099. 小于 K 的两数之和 | 简单 | 目标从「等于」放宽成「小于」，需在收缩过程中持续记录最优和 |
| 15. 三数之和 | 中等 | 多一层枚举 + 排序，还要在三个位置上分别跳过重复值以去重 |
| LCR 007. 三数之和 | 中等 | 与 15 同题，是本题「固定一个数 + 有序配对」思路的直接升级 |
| 16. 最接近的三数之和 | 中等 | 找不到精确解，改为在移动指针时维护与目标的最小差值 |
| 611. 有效三角形的个数 | 中等 | 判定条件变成不等式，命中时可一次性统计一整段区间的贡献 |
| 面试题 16.24. 数对和 | 中等 | 输入无序，需先排序再双指针，且要收集全部答案而非第一组 |