有序数组的两数之和怎么用双指针 O(n) 解决？

简化版

在有序数组里找两个数之和等于 target,用对撞指针:left 从头、right 从尾。看两数之和——太小就 left++(往大调),太大就 right--(往小调),相等就找到。因为数组有序,每次移动都能明确排除一批组合,一趟 O(n) 搞定,且只用 O(1) 空间。这比「排序后再哈希」或「暴力 O(n²)」都优——前提是数组已经有序。

详细版

int[] twoSum(int[] a, int target) {   // a 已升序排列
    int left = 0, right = a.length - 1;
    while (left < right) {
        int sum = a[left] + a[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;   // 和太小 → 左指针右移，增大和
        else right--;                     // 和太大 → 右指针左移，减小和
    }
    return new int[]{-1, -1};             // 没找到
}

left < right:两个指针不重叠(同一个数不能用两次)。
sum < target → left++:因为有序,右边已经是最大,只能让左边变大。
sum > target → right--:让右边变小。
时间 O(n)、空间 O(1)。

完整版教学

一、为什么有序是关键前提

对撞指针能解两数之和,完全依赖数组有序。有序意味着「指针移动方向」和「值变化方向」严格对应:left 右移一定让 a[left] 变大、right 左移一定让 a[right] 变小。于是当和不对时,我们能明确知道该往哪个方向调。如果数组无序,移动指针不知道值会变大还是变小,这个方法就失效了——无序数组的两数之和要用哈希表(O(n) 时间、O(n) 空间)。

二、为什么这样移动不会漏答案(正确性)

这是双指针最需要想清楚的点。假设当前 a[left] + a[right] < target:

a[right] 已经是当前右边界的最大值。a[left] 和「right 左边的任何数」相加,只会更小(那些数都 ≤ a[right])。
所以 a[left] 不可能和任何数凑出 target 了——可以彻底放弃 a[left],left++。

同理 sum > target 时,a[right] 和任何比 a[left] 大的数相加都更大,a[right] 出局,right--。每次移动都排除掉一整个元素的所有组合,所以不重不漏。这种「移动一步、排除一批」正是对撞指针 O(n) 的来源。

三、走一个例子

a = [2, 7, 11, 15]，target = 18：
left=0(2), right=3(15): 2+15=17 < 18 → left++
left=1(7), right=3(15): 7+15=22 > 18 → right--
left=1(7), right=2(11): 7+11=18 == 18 → 找到 (1,2)

指针相向逼近,一趟就定位。

四、和其它解法的对比

解法	前提	时间	空间
暴力双循环	无	O(n²)	O(1)
哈希表	无(可无序)	O(n)	O(n)
对撞指针	数组有序	O(n)	O(1)

无序数组 → 用哈希表(一边遍历一边查 target - a[i] 在不在)。
有序数组 → 用对撞指针,省掉哈希表的 O(n) 空间。
如果数组无序但允许排序,排序 O(n log n) 后再双指针也可以——但如果只求「是否存在」且不介意空间,哈希更快。

五、变体与延伸

对撞指针的两数之和是一个基础模块,很多题在它之上搭建:

三数之和 / 四数之和:固定一个(或两个)数,剩下的用对撞指针找两数之和,把 O(n³)/O(n⁴) 降一阶。
两数之和 ≤ / < target 的对数:和太大时 right--,和满足时 right - left 对都满足,一次性统计。
最接近的两数之和:记录过程中最接近 target 的和。

掌握这个基础的「有序 + 对撞」套路,一批题就通了。

六、易错点

循环条件 left < right:相等时是同一个元素,不能用两次;写成 <= 会出错。
必须有序:如果题目没说有序,先确认或先排序,否则方法不成立。
返回下标还是值、下标从 0 还是 1,看题目要求(LeetCode 167 返回从 1 开始的下标)。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：在有序数组中，当前和偏小时所有以 left 为端点且右端更左的组合都更小，可整体排除。

对应的状态推进是：和小则 left++，和大则 right—，相等即命中。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。两指针总共最多移动 n-1 次，O(n)。

带数字走一遍：[2,7,11,15] 查 9，首轮即由 2+15 过大右移，再命中 2+7。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	前提是数组有序；返回下标时注意题目要求 0-based 还是 1-based
时间复杂度	O(n)
额外空间	O(1)
关键边界	求和可能溢出；有重复且要求全部答案时不能命中即停
替代方案	无序数组通常用哈希 O(n)，或排序后保留原下标

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“前提是数组有序；返回下标时注意题目要求 0-based 还是 1-based”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“两指针总共最多移动 n-1 次，O(n)”。
误区：重复值和边界值不会改变代码。 求和可能溢出；有重复且要求全部答案时不能命中即停。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“在有序数组中，当前和偏小时所有以 left 为端点且右端更左的组合都更小，可整体排除”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[2,7,11,15] 查 9，首轮即由 2+15 过大右移，再命中 2+7”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“无序数组通常用哈希 O(n)，或排序后保留原下标”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

有序数组两数之和用对撞指针:left 头、right 尾,和太小 left++(增大)、太大 right--(减小)、相等命中,O(n) 时间、O(1) 空间。正确性:有序保证「移动方向=值变化方向」,和不对时能排除掉一整个元素的所有组合,不重不漏。前提是有序(无序用哈希表 O(n) 空间)。它是三数之和、最接近之和等题的基础模块。循环条件用 left < right。

简化版

详细版