数据结构与算法 / 系统课时
用相向双指针缩小候选区间
用相向双指针缩小候选区间
相向双指针不是简单地把两个下标放在数组两端,而是利用单调性证明:每移动一次左指针或右指针,都能安全排除一批不可能成为答案的候选。掌握这个判断依据后,许多平方级枚举可以压缩成一次线性扫描。
学习目标
- 识别适合从两端向中间收缩的单调关系
- 理解每次移动一个指针为什么不会漏掉正确答案
- 能把相向双指针迁移到有序数组、回文和两端决策问题
双指针真正利用的是可排除性
相向双指针通常从 left = 0、right = n - 1 开始,并在 left < right 时持续移动。关键问题不是“该移动哪边”,而是当前信息能否证明某一整批候选都不再需要检查。
以升序数组的两数之和为例。若 nums[left] + nums[right] < target,右端已经是当前范围内最大的数。保持 left 不动并把 right 向左移动,只会让和更小,因此当前 left 不可能与区间内任何元素组成目标值,可以直接执行 left += 1。
反过来,如果当前和大于目标值,左端已经是范围内最小的数。保持 right 不动而增大左端只会让和更大,所以当前 right 也可以被整体排除。

因此,双指针能够达到 O(n) 的根本原因,是每一步都删除至少一个以后无需再考虑的端点,而不是一次只试一个独立组合。
用有序数组两数之和建立套路
下面实现一个完整例子:数组已经按升序排列,返回两个数的 1-based 下标。如果不存在答案,则返回空列表。
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
current = nums[left] + nums[right]
if current == target:
return [left + 1, right + 1]
if current < target:
# 当前左端过小,它与区间内任何元素都无法达到 target。
left += 1
else:
# 当前右端过大,它与区间内任何元素都不会得到更小的目标和。
right -= 1
return []
if __name__ == "__main__":
numbers = [2, 7, 11, 15]
print(two_sum_sorted(numbers, 18))预期输出
[2, 3]两个指针最多各移动 n - 1 次,因此时间复杂度为 O(n),额外空间复杂度为 O(1)。如果改用两层循环枚举所有数对,最坏情况下需要 O(n^2) 次比较。
判断能不能安全移动指针
看到“两端”“有序”“回文”并不意味着一定能套双指针。真正需要检查的是:根据当前比较结果,能否证明移动某一端不会错过答案。
对有序两数之和,数组顺序保证了和随端点移动具有单调性;对回文判断,如果两端字符相同,就只需继续检查内部子串,如果不同则可以立即失败;对盛最多水的容器,面积受较短边限制,因此移动较长边不能改善当前短板,而移动较短边才可能得到更高的边界。
这些问题表面不同,但推理形式一致:先找出当前状态中的限制因素,再移动那个能够消除限制、同时安全舍弃旧候选的指针。
常见错误来自没有证明排除条件
最常见的问题是凭感觉移动指针。例如两数之和中,如果数组没有排序,就不能根据“当前和偏小”推出应该移动左指针,因为右侧元素未必更大,候选空间没有单调性。
另一个错误是循环条件写成 left <= right。当题目要求选择两个不同位置时,两个指针相遇后已经没有合法数对,所以应使用 left < right。如果题目允许单个中心元素参与判断,例如某些回文扫描,则相遇时无需额外比较,也仍可在 left < right 时结束。
做相向双指针题时,先不要急着写 left++ 或 right--。先用一句话证明“为什么这一侧可以永久丢弃”。只要这个排除证明成立,双指针就不是技巧性的猜法,而是一种利用单调性持续缩小搜索空间的确定性算法。