数据结构与算法 / 系统课时

用相向双指针缩小候选区间

用相向双指针缩小候选区间

相向双指针不是简单地把两个下标放在数组两端,而是利用单调性证明:每移动一次左指针或右指针,都能安全排除一批不可能成为答案的候选。掌握这个判断依据后,许多平方级枚举可以压缩成一次线性扫描。

学习目标

  • 识别适合从两端向中间收缩的单调关系
  • 理解每次移动一个指针为什么不会漏掉正确答案
  • 能把相向双指针迁移到有序数组、回文和两端决策问题

双指针真正利用的是可排除性

相向双指针通常从 left = 0、right = n - 1 开始,并在 left < right 时持续移动。关键问题不是“该移动哪边”,而是当前信息能否证明某一整批候选都不再需要检查。

以升序数组的两数之和为例。若 nums[left] + nums[right] < target,右端已经是当前范围内最大的数。保持 left 不动并把 right 向左移动,只会让和更小,因此当前 left 不可能与区间内任何元素组成目标值,可以直接执行 left += 1。

反过来,如果当前和大于目标值,左端已经是范围内最小的数。保持 right 不动而增大左端只会让和更大,所以当前 right 也可以被整体排除。

相向双指针依据和的大小收缩候选区间

因此,双指针能够达到 O(n) 的根本原因,是每一步都删除至少一个以后无需再考虑的端点,而不是一次只试一个独立组合。

用有序数组两数之和建立套路

下面实现一个完整例子:数组已经按升序排列,返回两个数的 1-based 下标。如果不存在答案,则返回空列表。

python
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))

预期输出

text
[2, 3]

两个指针最多各移动 n - 1 次,因此时间复杂度为 O(n),额外空间复杂度为 O(1)。如果改用两层循环枚举所有数对,最坏情况下需要 O(n^2) 次比较。

判断能不能安全移动指针

看到“两端”“有序”“回文”并不意味着一定能套双指针。真正需要检查的是:根据当前比较结果,能否证明移动某一端不会错过答案。

对有序两数之和,数组顺序保证了和随端点移动具有单调性;对回文判断,如果两端字符相同,就只需继续检查内部子串,如果不同则可以立即失败;对盛最多水的容器,面积受较短边限制,因此移动较长边不能改善当前短板,而移动较短边才可能得到更高的边界。

这些问题表面不同,但推理形式一致:先找出当前状态中的限制因素,再移动那个能够消除限制、同时安全舍弃旧候选的指针。

常见错误来自没有证明排除条件

最常见的问题是凭感觉移动指针。例如两数之和中,如果数组没有排序,就不能根据“当前和偏小”推出应该移动左指针,因为右侧元素未必更大,候选空间没有单调性。

另一个错误是循环条件写成 left <= right。当题目要求选择两个不同位置时,两个指针相遇后已经没有合法数对,所以应使用 left < right。如果题目允许单个中心元素参与判断,例如某些回文扫描,则相遇时无需额外比较,也仍可在 left < right 时结束。

做相向双指针题时,先不要急着写 left++ 或 right--。先用一句话证明“为什么这一侧可以永久丢弃”。只要这个排除证明成立,双指针就不是技巧性的猜法,而是一种利用单调性持续缩小搜索空间的确定性算法。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用相向双指针缩小候选区间

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通