LeetCode（二）：双指针技巧

哈希表靠内存换速度，双指针则反其道而行之：只需一点结构性假设——数组已排序、链表可能存在环、答案落在某个连续窗口内——就能以 $$O(n)$$ 时间复杂度和 $$O(1)$$ 额外空间解决问题。代码看起来极其简单（两个下标加一个 while 循环），但却是新手最容易翻车的技巧之一：下标越界、死循环、漏掉重复项、平局时移错指针……各种陷阱层出不穷。要真正掌握它，关键不是死记移动规则，而是围绕 不变量 进行严谨推理。

本文将双指针归纳为四种核心模式：对撞指针、快慢指针、滑动窗口 和 分区指针，并分别对应一道高频面试题：Two Sum II、盛最多水的容器、3Sum、环形链表（LeetCode 141）以及移动零。

双指针为什么有效#

在长度为 $$n$$ 的数组中暴力枚举所有数对，时间复杂度是 $\Theta(n^2)$ ——每一对都要检查一次。而双指针能在某些场景下将复杂度降至 $\Theta(n)$ ，其核心在于：每次比较都能一次性排除一大片搜索空间，而非仅剔除单个候选。

利用的结构性质	模式	每次比较排除的内容
数组有序	对撞指针	所有包含被舍弃端点的数对
快指针可在有限环中追上慢指针	快慢指针	所有非环上的节点
合法性随窗口长度单调变化	滑动窗口	相同右边界下更小的窗口
每个值属于 $$k$$ 个区域之一	分区指针（k路）	已分类的前缀和后缀

这四种模式本质上都在说同一件事：一次比较能砍掉一块区域，而不只是一个点。一旦这个性质不成立（如数组无序、无环、合法性非单调、无法清晰分区），双指针就会退化回 $$O(n^2)$$ ，甚至得出错误结果。

模式一 —— 对撞指针（有序数组）#

不变量#

left 和 right 从数组两端出发，相向而行。维护的核心不变量是：

若解存在，则必在闭区间 [left, right] 内。

每次比较要么命中答案，要么可安全排除某一端的元素。被排除端的指针移动，另一端保持不动。

LeetCode 167 —— 两数之和 II#

给定一个升序数组 numbers（1-indexed）和目标值 target，返回唯一满足 a + b = target 的两个数的 1-based 下标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    """在升序数组中找到唯一一对和为目标值的元素，返回其 1-based 下标。"""
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        if s < target:
            left += 1          # 和偏小，丢掉当前最小值
        else:
            right -= 1         # 和偏大，丢掉当前最大值
    return []                  # 题目保证有解，理论上不会到这里

为何 s < target 时移动左指针是安全的？ 假设当前和 s = numbers[left] + numbers[right] < target。由于数组有序，numbers[left] 与 [left+1, right] 中任意元素之和都不超过 s，因此不可能达到 target。这意味着所有以 left 为左端点的组合均可一次性排除——相当于在数对矩阵中直接划掉整行 left × [left+1..right]。s > target 时同理，移动右指针即可。

复杂度：时间 $$O(n)$$ ，空间 $$O(1)$$ 。每轮至少有一个指针向中心移动，相遇即终止。

LeetCode 11 —— 盛最多水的容器#

给定高度数组 $h_0, h_1, \dots, h_{n-1}$ ，选择 $$i < j$$ 使得面积 $(j - i) \cdot \min(h_i, h_j)$ 最大。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def max_area(height: list[int]) -> int:
    """两条竖线和 x 轴围成的最大矩形面积。"""
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h = min(height[left], height[right])
        best = max(best, (right - left) * h)
        # 移动较短的那一边：这是唯一可能让面积变大的方向
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

贪心正确性的关键：设当前 $h_i \le h_j$ 。对于任意 $$k < j$$ ，子容器 $$(i, k)$$ 的宽度更小，且高度 $\min(h_i, h_k) \le h_i$ ，因此面积至多为 $(j - i) \cdot h_i$ ——这正是当前记录的值。换言之，以 $$i$$ 为左边界的所有组合都不可能更优，故可安全舍弃 $$i$$ 。右侧情况对称。

值得牢记的是：移动短边并不保证下一步面积更大，但能确保被舍弃的那一端不会再出现更优解。这一点足以保证贪心策略的正确性。

LeetCode 15 —— 三数之和#

返回所有和为 0 的唯一三元组 [a, b, c]。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def three_sum(nums: list[int]) -> list[list[int]]:
    """返回所有和为 0 的不重复三元组。"""
    nums.sort()                                # O(n log n)，为对撞指针做准备
    n = len(nums)
    result: list[list[int]] = []

    for i in range(n - 2):
        # 剪枝：当前最小值大于 0，直接退出
        if nums[i] > 0:
            break
        # 第一位去重
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1
        target = -nums[i]
        while left < right:
            total = nums[left] + nums[right]
            if total == target:
                result.append([nums[i], nums[left], nums[right]])
                # 记录答案后，第二、三位去重
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1
    return result

三个去重位置，缺一不可。排序使重复值相邻，算法需在每一层选择时跳过重复段：

第一层：if i > 0 and nums[i] == nums[i - 1]: continue，避免重复选取相同的首元素；
第二层：找到解后，left 向右跳过所有等于刚使用值的元素；
第三层：同理，right 向左跳过重复值。

漏掉任一环节，输入如 [-2, 0, 0, 2, 2] 就会产生重复结果。虽然可用 set 兜底去重，但会带来额外 $O(\log n)$ 插入开销，并掩盖算法本质。

复杂度：排序 $O(n \log n)$ ，外层循环 $$O(n)$$ ，内层双指针扫描 $$O(n)$$ ，总计 $$O(n^2)$$ 时间， $O(\log n)$ 空间（排序递归栈）。

模式二 —— 快慢指针（Floyd 龟兔赛跑）#

不变量#

两指针沿同一序列以不同速度移动（通常慢指针走 1 步，快指针走 2 步）。核心不变量为：

若存在环，快指针必在环内追上慢指针；若无环，快指针先抵达终点。

原理纯属算术：进入环后，快慢指针间距每轮减少 1，因此最多 $\lambda$ 轮（ $\lambda$ 为环长）内必然相遇。

LeetCode 141 —— 环形链表#

给定链表，判断是否存在环，要求 $$O(1)$$ 额外空间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None) -> None:
        self.val = val
        self.next = next

def has_cycle(head: ListNode | None) -> bool:
    """判断链表是否有环。O(1) 额外空间。"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

为何必然相遇？ 设非环部分长 $\mu$ ，环长 $\lambda$ 。当两指针均入环后，快指针相对慢指针每轮缩短距离 1。无论初始偏移 $d \in \{1, 2, \dots, \lambda - 1\}$ 是多少，最多 $$d$$ 轮后即相遇。总步数不超过 $\mu + \lambda$ ，故时间复杂度 $$O(n)$$ ，空间 $$O(1)$$ 。

为何必须是 1 vs 2？ 任意速度对 $$(a, b)$$ （ $$a < b$$ ）只要满足 $\gcd(b - a, \lambda) = 1$ 即可。但 $$(1, 2)$$ 的优势在于 $$b - a = 1$$ 恒整除 $\lambda$ ，因此无论环长如何都保证正确——无需担心数论陷阱。

找环入口（LeetCode 142）#

当 slow 与 fast 在环内某点 m 相遇后，将一指针重置至 head，两者均以 1 步/轮前进，再次相遇处即为环入口。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def detect_cycle(head: ListNode | None) -> ListNode | None:
    """返回环的入口节点，若无环则返回 None。"""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # 第二阶段：从头节点派一个新指针，和 slow 同速前进
            entry = head
            while entry is not slow:
                entry = entry.next
                slow = slow.next
            return entry
    return None

入口结论的一句话证明：相遇时，slow 走了 $\mu + k$ 步，fast 走了 $2(\mu + k)$ 步，二者位于同一点 ⇒ 差值 $\mu + k$ 是 $\lambda$ 的整数倍。因此，从 head 走 $\mu$ 步，与从相遇点走 $\mu$ 步，均会到达环入口——它们在此重逢。

模式三 —— 滑动窗口#

不变量#

窗口 $$[l, r]$$ 覆盖数组或字符串，其“合法性”由特定约束定义（如无重复字符、和 $\ge k$ 、包含所有目标字符等）。滑动窗口有效的前提是合法性具有单调性：

若 $$[l, r]$$ 非法，则任何包含它的更大窗口 $$[l, r']$$ （ $r' \ge r$ ）也非法（反之亦然）。

该性质确保 left 指针永不回退。每个元素最多被 right 和 left 各访问一次，总时间复杂度 $$O(n)$$ 。

LeetCode 3 —— 无重复字符的最长子串#

给定字符串，求不含重复字符的最长子串长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def length_of_longest_substring(s: str) -> int:
    """返回字符串 s 中无重复字符的最长子串长度。"""
    last_seen: dict[str, int] = {}  # 字符 -> 它在 s 中最近出现的位置
    left = 0
    best = 0
    for right, ch in enumerate(s):
        # 如果当前字符在窗口内已经出现过，就把左边界移动到它的下一个位置。
        # max(...) 很关键：之前的重复可能已经把 left 推得更靠右了。
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

>= left 守卫的必要性（以 “abba” 为例）：当 right = 2（第二个 b）时，left 被设为 2。当 right = 3（第二个 a）时，last_seen['a'] = 0 已在当前窗口 [2, 3] 之外。若无 >= left 判断，left 会错误回退至 1，破坏“永不回退”不变量，导致错误结果。

复杂度：时间 $$O(n)$$ （每个字符至多进出窗口各一次），空间 $O(\min(n, |\Sigma|))$ （字符集大小限制）。

模式四 —— 分区指针（k 路）#

不变量#

以三指针 lo、mid、hi 将数组划分为四段（以荷兰国旗问题为例）：

[0, lo) 为已确定的“低”值；[lo, mid) 为已确定的“中”值；[mid, hi] 为未处理部分；(hi, n) 为已确定的“高”值。

每步处理 arr[mid]，根据其值决定交换至低区、保留原位或交换至高区，同时维持不变量。

LeetCode 75 —— 颜色排序（荷兰国旗）#

给定仅含 0、1、2（红、白、蓝）的数组，原地排序为红-白-蓝顺序，要求一趟完成。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def sort_colors(nums: list[int]) -> None:
    """原地排序仅含 0/1/2 的数组，时间 O(n)，空间 O(1)。"""
    lo, mid, hi = 0, 0, len(nums) - 1
    while mid <= hi:
        v = nums[mid]
        if v == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1
            mid += 1                  # 换上来的值来自 [lo, mid)，按不变量已经是 1，直接跳过
        elif v == 2:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1                   # 注意：mid 不动，换上来的值还没处理
        else:                         # v == 1
            mid += 1

0 分支与 2 分支的不对称性是最易错细节：交换至低区时，被换出的值来自 [lo, mid)，按不变量必为 1，可安全推进 mid；但交换至高区时，被换出的值来自 [mid+1, hi]（未分类区），必须留待下轮处理，故 mid 不能推进。此细节一旦忽略，代码必崩。

LeetCode 283 —— 移动零（k=2 分区）#

将所有 0 移至末尾，保持非零元素相对顺序，原地操作。

退化为两区域：[0, write) 存放按序排列的非零值，[write, n) 为其余部分。

1
2
3
4
5
6
7
def move_zeroes(nums: list[int]) -> None:
    """把所有 0 移到数组末尾，保持非零元素的相对顺序。"""
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

采用交换而非直接赋值，是为了确保第二区域始终为 0：每次将非零值前移时，留下的位置必为 0——因为通过归纳法可知，区间 [write, read) 内的位置已被清零。

哈希表 vs 双指针：何时选择排序？#

一张大家想要却少见的对比表：

问题	哈希表	双指针
找一对和为 $$T$$ （不要求原下标）	$$O(n)$$ 时间， $$O(n)$$ 空间	$O(n \log n) + O(n)$ ， $$O(1)$$ 额外空间
找一对，必须返回原下标	哈希表胜出	需排序时携带原下标数组， $$O(n)$$ 额外空间
找所有对/三元组/四元组	去重繁琐	$O(n^{k-1})$ ，通过跳过重复段干净去重
检测链表环	$$O(n)$$ 额外空间	$$O(1)$$ —— Floyd
最长合法连续区间	常非必需	滑动窗口是标准解法

决策准则：若需原下标、或数组无序且禁止排序，选哈希表；若数据已有序（或可排序）、答案需连续、或必须 $$O(1)$$ 空间，则选双指针。

五种常见翻车（及规避方法）#

模式识别容易，写对循环才是难点。以下是毁掉面试的五大高频错误：

1. 平局时移错指针：在“盛水容器”中，若移动较高边，高度上限不变但宽度缩小，结果只会更差。应移动较短边；若相等，任选其一。

2. 命中后忘记推进：3Sum 中找到解后，必须同时移动 left 和 right，否则会无限重测同一对。推进需配合去重 while 循环。

3. 滑动窗口中 left 回退：left = last_seen[ch] + 1 若无 max(left, ...) 保护，在 “abba” 上会出错。要么用 max 防回退，要么显式删除字符。

4. 忽略 fast.next 检查：访问 fast.next.next 前必须确保 fast 和 fast.next 均非空。仅检查 fast 会在两节点链表上崩溃。

5. 荷兰国旗中高分支误推 mid：这是分区指针最常见错误。牢记：低分支推进 mid，高分支不推进。

面试沟通#

一套话术可拿下 80% 分数：

“本题数组有序 / 需找连续窗口 / 明显是链表环问题，因此我选用 <具体模式>。暴力解法为 $$O(n^2)$$ ，而双指针可达 $$O(n)$$ ，因每次比较能排除整行/整列/前缀。我将维护的不变量是 <明确描述不变量>。我会预先处理边界情况：空输入、单元素、全等值等。”

在编码前阐明不变量，是向面试官证明你理解本质而非死记模板的最佳信号。此举几乎总能赢得加分。

练习题#

LeetCode #	题目	模式	难度
167	两数之和 II - 输入有序数组	对撞指针	简单
283	移动零	分区（k=2）	简单
141	环形链表	快慢指针	简单
11	盛最多水的容器	对撞 + 贪心	中等
15	三数之和	排序 + 对撞	中等
75	颜色分类	分区（k=3）	中等
142	环形链表 II	快慢 + 数论	中等
3	无重复字符的最长子串	滑动窗口	中等
209	长度最小的子数组	滑动窗口	中等
76	最小覆盖子串	滑动窗口	困难

参考文献#

Robert Floyd, Nondeterministic Algorithms, J. ACM 14(4), 1967 —— 环检测算法原始论文。
Cormen 等，《算法导论》，第 8 章 —— 快排与荷兰国旗的分区理论基础。
Donald Knuth, TAOCP Vol. 2, §3.1 —— rho 算法（“龟兔赛跑”最初应用）。

下一步#

快慢指针的思想将在第三篇：链表操作中以新面貌出现——找中点、切分链表用于归并排序、按 k 个一组反转，背后皆有其影子。对撞指针思路亦可直接迁移至链表回文判断。而让这些技巧融会贯通的关键，则是一个虚拟头节点——具体如何运用，下一篇揭晓。

LeetCode（二）：双指针技巧

双指针为什么有效#

模式一 —— 对撞指针（有序数组）#

不变量#

LeetCode 167 —— 两数之和 II#

LeetCode 11 —— 盛最多水的容器#

LeetCode 15 —— 三数之和#

模式二 —— 快慢指针（Floyd 龟兔赛跑）#

不变量#

LeetCode 141 —— 环形链表#

找环入口（LeetCode 142）#

模式三 —— 滑动窗口#

不变量#

LeetCode 3 —— 无重复字符的最长子串#

模式四 —— 分区指针（k 路）#

不变量#

LeetCode 75 —— 颜色排序（荷兰国旗）#

LeetCode 283 —— 移动零（k=2 分区）#

哈希表 vs 双指针：何时选择排序？#

五种常见翻车（及规避方法）#

面试沟通#

练习题#

参考文献#

下一步#

LeetCode 算法模式 10 篇

读有所得？