双指针技巧

2026-06-02

一句话: 用两个指针的相对运动,把 暴力压成 。 之所以能压,是因为问题里藏着单调性 — 移动一个指针让”目标”单调变化,所以根本不需要回头。

直觉 — 两指针的单调运动

暴力两层循环之所以浪费,是因为它每次内层都从头扫一遍,把”已经知道不行”的组合又试了一次。双指针不一样: 每移动一步,都基于上一步学到的信息,永不回头。

为什么能不回头? 因为问题里有单调性:

  • 对撞: 数组排好序 → 移动 left 一定让 sum 变大,移动 right 一定让 sum 变小。
  • 快慢: 两指针速度差恒定 → 相对位移随时间单调增长,该撞会撞,该追会追。

两个指针,各自只走 N 步,合起来 。下面动画里,看绿色 / 红色指针怎么”逼近”和”追逐”:

对照动画再读下面三种模式,印象会深一倍。

三种模式 — 对撞 / 快慢 / Floyd

模式 起点 运动 利用的单调性 典型题
对撞 两端 向中间逼近 数组有序,sum 随移动单调变 两数之和 II, 三数之和, 验证回文
快慢 同起点 / 错开 同向不同速 速度差恒定 → 相对位移单调 链表中点, 原地去重
Floyd 同起点 同向, fast 走 2 步 环内必追上(模 L 周期) 141 环形链表, 142 找环入口

记忆抓手: 对撞看 sum, 快慢看距离差, Floyd 看周期。

为什么对撞可以”丢”一整列

数组有序时, 若 nums[left] + nums[right] < target, 那 left 配剩下任何比 right 小的数都还是更小, 一整列直接淘汰 → 只能 left++。反之 right--。每次淘汰一行或一列, 所以 N 步走完。

为什么”盛最多水”要移短板(LeetCode 11)

给定高度数组 height,第 根竖线两端是 和 。选两根线和 x 轴围成容器,求最大盛水量。

容量取决于宽和短板:

两指针 从两端起步,每步移走较矮的那根线。为什么这样不会漏掉最优?

关键引理: 设当前 (左边是短板)。让 不动、把右指针缩到任意 ,容量一定严格变小:

(第一步: 高度 ;第二步: 宽度 。)

  • 宽: ,严格变小。
  • 高: 高度被短板 锁死, 再高也只能取到 ,更矮则更小,所以 。

含义: 短板 配右侧任何线,最大就是当下的 —— 它的潜力已用尽,留着只会越移越小。所以安全地丢掉它 left++。对称地 时丢右边 right--。

短板 i j 水位 = min(h[i], h[j]) = h[i] 移短板

移高的那根:宽变小、水位仍被短板卡住 → 纯亏;只有移短板才可能解锁更高水位。

循环不变量: 全局最优对始终在当前 窗口内。被丢的线对(短板配窗口内任意线)容量都 已记录的 ,所以最优不会被丢掉;窗口每步宽 , 步收完 → 。

这跟上面”丢一整列”同构: 那里丢的是有序数组的一行/一列,这里丢的是短板能配的所有线对。

为什么快慢能找中点

slow 走 1 步, fast 走 2 步。fast 到尾时, slow 正好在一半位置 — 距离差以 1 的速率单调增长, 二者的”时间差”就是答案。

模板 — Python 各一份

对撞: 两数之和 II

1
2
3
4
5
6
7
8
9
10
def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1

快慢: 链表中点

1
2
3
4
5
6
def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

快慢: 原地去重(口诀: slow 指向”下一个要写的位置”)

1
2
3
4
5
6
7
8
def remove_duplicates(nums):
    if not nums: return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

Floyd: 判环 + 找环入口

1
2
3
4
5
6
7
8
9
10
def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast:           # 有环, 进入第二阶段
            slow = head
            while slow != fast:
                slow, fast = slow.next, fast.next
            return slow            # 环入口
    return None

Floyd 为什么 work — 把那行数学拆开

先把记号钉死(对照动画里的尾巴 + 环):

  • : 头到环入口的距离,也就是尾巴长度。
  • : 环入口到相遇点的距离,沿指针前进方向量。
  • : 环长。

第一阶段: 为什么撞得上,而且 slow 还没绕满一圈

两人都进环之后,slow 每步 1 格、fast 每步 2 格 —— fast 相对 slow 每轮多走 1 格。

把”fast 还要走多远才追上 slow”这段环上距离记成 (沿前进方向量)。它有两条铁律:

  • : 这纯粹因为环长是 ,环上任意两点的距离都不可能 ,跟在哪进环无关。
  • 每走一步 精确减 1: fast 每轮追近 1 格;又因为相对步长恰好是 1,fast 不会”跳过”slow,只会精确落在 那一格(所以一定相遇,不会擦肩)。
环长 = L 前进方向 D ≤ L-1 S slow F fast

每步 D 减 1,且绝不越过 0 ⇒ 至多 L-1 步就在 D=0 处相遇。

合起来: 从 出发、每步减 1,最多 步就 相遇。而这 步里 slow 也只走了同样多步 —— 连一圈( 步)都没走满。这正是下一段”slow 总路程恰好是 、没有绕圈项”的依据。

相遇时,各自走了多远?

  • slow: 由上一节,它走不满一圈就被追上(那 步正好就是 ),所以总路程就是 。
  • fast: 速度翻倍,路程是 slow 的两倍,即 。
  • 但 fast 的路程还能换个角度数: 先花 走到入口,再在环里绕了 整圈又走 到相遇点,即 ( 是它多绕的圈数,)。

同一段路程的两种写法,画等号:

两边同时减掉 :

第二阶段: 为什么相遇后能定位入口?

翻译成人话: 从相遇点再走 步 = 绕环 整圈再退回 ,终点正好是环入口。 而从 head 出发走 步,显然也到入口。

所以模板第二阶段才那么写: 让一个指针回到 head,两个指针都改成每步 1 格、同时出发,走完 步双双落在入口 — 这是 逼出来的必然,不是凑巧。

动画里绿色 slow 和红色 fast 在环里相遇的那一格,它到环入口的距离就是 。

经典题

热身 — 三种模式各刷一道, 形成肌肉记忆:

进阶 — 都是”想清楚单调性在哪”的练习:

思考题

对撞指针为什么要求数组有序? 无序时怎么办?

有序 → 单调性 → 每次移动都在确定地缩小搜索空间。无序时这条死。退路两条: 哈希表( 时间 + 空间), 或者先排序再对撞( 时间, 额外空间)。看题目要哪个权衡。

Floyd 中, slow 回到 head 后为什么两指针同速就能在入口相遇?

因为 。从相遇点走 步 = 绕环 圈再退 = 入口。从 head 走 步也到入口。两人同速、同时间, 必在入口相遇。这就是 Floyd 第二阶段的全部魔法。

原地去重要保留最多 2 个相同元素怎么改?

把比较对象往前看一位: nums[fast] != nums[slow - 1]。即 slow 看的是”上上次写入的值”,新来的只要和它不同就允许写。

1
2
3
if fast < 2 or nums[fast] != nums[slow - 1]:
    slow += 1
    nums[slow] = nums[fast]

保留 个就比较 nums[slow - (k-1)]。模式通用。

记忆法

一句话: 两指针朝一个方向走, 让目标单调变化, 永不回头。

三种模式 + 关键词:

模式 关键词 触发信号
对撞 有序 + sum “两数和 / 容器 / 回文”
快慢 速度差 “中点 / 去重 / 移零”
Floyd 周期 “链表有没有环 / 找入口 / 重复数”

看到题, 先问: 有单调性吗? 在哪一维? 答出来了, 双指针就是顺手的事。