哈希表是用空间换时间，双指针正好相反：用一点结构假设（数组有序、链表可能成环、答案落在某个连续窗口里），换来 $O(n)$ 时间和 $O(1)$ 额外空间。代码看起来再朴素不过——两个下标、一个 while 循环——但它是新手最容易踩坑的技巧：下标差一、死循环、漏掉去重、平手时移错指针。真正能把这些坑填掉的，不是死记移动规则，而是用循环不变量去思考。

本文把双指针拆成四种风格——对撞指针、快慢指针、滑动窗口、分区指针——每种都配一道面试常客：Two Sum II、3Sum、盛最多水的容器、环形链表、移动零。

系列导航

LeetCode 算法精讲系列（共 10 篇）：

哈希表 —— 两数之和、最长连续序列、字母异位词分组
→ 双指针技巧 —— 对撞、快慢、滑动窗口、分区 ← 当前文章
链表操作 —— 反转、找环入口、合并
二叉树遍历与构造 —— 中序/前序/后序、最近公共祖先
动态规划入门 —— 一维/二维 DP、状态转移
回溯算法 —— 排列、组合、剪枝
二分查找 —— 索引二分、答案二分、实数二分
栈与队列 —— 单调栈、优先队列、双端队列
图算法 —— BFS / DFS、拓扑排序、并查集
贪心与位运算

双指针为什么管用

长度为 $n$ 的数组上暴力枚举所有数对是 $\Theta(n^2)$，每对都看一次。双指针之所以能压到 $\Theta(n)$，是因为比较一次就能砍掉一整片候选，而不是只排除一个候选：

利用的结构事实	模式	一次比较砍掉的候选
数组已经有序	对撞指针	经过被淘汰那个端点的所有对
在有限环里，快指针能套圈慢指针	快慢指针	所有非环节点
合法性关于窗口长度单调	滑动窗口	同一右端点下所有更小的窗口
每个值落入 $k$ 个区域之一	分区指针	已分类的前缀和后缀

四种模式的共同骨架：一次比较干掉的是一片，不是一个。当这条性质不成立时（数组无序、不成环、合法性非单调、不存在干净的分区），双指针就退化回 $O(n^2)$ 甚至直接错误。

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

不变量

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

答案如果存在，必定落在闭区间 [left, right] 内。

每次比较要么命中当前对，要么排除掉两端中的一个元素。被排掉那一端的指针前进，另一端不动。

LeetCode 167 —— Two Sum II

题意。 给定升序数组 numbers（题目按 1 起始下标）和 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]:
    """在升序数组里找唯一一对和为 target 的值，返回 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] 里任何一个数配对，结果都 $\le s < \text{target}$。也就是说，所有以 left 为左端点的对都不可能命中——这一整行配对都被排除了，不只是 (left, 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$。考虑所有以 $i$ 为左端点的其他对 $(i, k)$（$k < j$）：宽度 $(k - i) < (j - i)$ 严格变小，高度 $\min(h_i, h_k) \le h_i$ 不会超过当前高度上限——所以面积不超过 $(j - i) \cdot h_i$，正好就是我们刚刚记下的那个值。结论：以 $i$ 为左端点的所有对都不可能更优，下标 $i$ 可以放心丢掉。右边对称。

值得记住的是：不是说下一对一定更大，而是说被丢掉那一端做端点的所有对都不可能更大。这就够保证贪心正确。

LeetCode 15 —— 3Sum

题意。 返回所有不重复三元组 [a, b, c]，满足 a + b + c == 0。

 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)
    out: list[list[int]] = []

    for i in range(n - 2):
        # 剪枝 1：当前最小值已经为正，三个非负数不可能和为 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:
            s = nums[left] + nums[right]
            if s == target:
                out.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 s < target:
                left += 1
            else:
                right -= 1
    return out

三处去重，缺一不可。 排序把重复值聚到一起；算法在每个槽位选值时，都得走过这段重复区间：

第一位。 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$ 轮（环长）必然相遇。

LeetCode 141 —— 环形链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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 is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

为什么相遇是必然的。 设入环前的尾巴长度为 $\mu$，环长为 $\lambda$。两指针都进入环之后，fast 相对 slow 在环上的偏移（模 $\lambda$）每轮严格减 1。从任意非零偏移 $d \in \{1, 2, \dots, \lambda - 1\}$ 出发，$d$ 轮后偏移归零。所以总轮数 $\le \mu + \lambda$，时间 $O(n)$，空间 $O(1)$。

为什么是 1 vs 2，不是 1 vs 3 或 1 vs 5？ 任意速度对 $(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:
            # 第二阶段：从 head 派一个新指针，和 slow 同速前进
            entry = head
            while entry is not slow:
                entry = entry.next
                slow = slow.next
            return entry
    return None

入口结论的一行证明�� 相遇时，慢指针走了 $\mu + k$ 步（$0 \le k < \lambda$），快指针正好两倍 $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):
        # 只有当这个字符的上次出现还在窗口内时，才需要把 left 跳过去。
        # 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

用 "abba" 演示 >= left 这一道防线。 right = 2（第二个 b）时，left 推到 2。right = 3（第二个 a）时，last_seen['a'] = 0 已经在当前窗口 [2, 3] 之外。如果不加 >= left 这层判断，left 就会倒退回 1，违反"永不回头"的不变量，结果直接错。

复杂度。 时间 $O(n)$（每个字符进出各一次），空间 $O(\min(n, |\Sigma|))$。

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

不变量

在同一个数组里维护 $k$ 个区域。$k = 3$ 是经典的荷兰国旗问题，三指针 lo、mid、hi 把数组切成：

[0, lo) 是已经放好的"低"值；[lo, mid) 是已经放好的"中"值；[mid, hi] 是未处理；(hi, n) 是已经放好的"高"值。

每一步处理 arr[mid]，要么换到低区、要么留在中区、要么换到高区——同时维持上述切分。

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

 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+1, hi]，还没分类，下一轮必须再看一次，所以 mid 不动。

LeetCode 283 —— 移动零（k = 2 的退化版）

两区域版本：[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

这里用 swap 而不是直接赋值，是因为要保证第二段始终是 0：每次往前拉一个非零值，留下的那一格必然是 0——位置 [write, read) 全是 0，这一点可以归纳出来。

哈希表 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 兜底，要么 left 走过的字符显式从计数里删掉。

4. fast.next 没判空。 fast.next.next 要求 fast 和 fast.next 都非空。只判 fast 会在两节点链表上崩。务必两个一起判。

5. 荷兰国旗里 mid 在 2 分支误前进。 分区指针最常翻的车。死记一句话：low 分支推 mid，high 分支不推。

面试沟通

下面这套话术能拿到任意双指针题的 80% 分：

“数组是有序的 / 答案是连续窗口 / 这是链表环检测，我倾向用 <某种模式>。暴力是 $O(n^2)$，双指针能压到 $O(n)$，因为每次比较能砍掉一整行/一整列/一整段前缀，而不是一个候选。我维护的不变量是 <把不变量说出来>。需要先处理的边界：空输入、单元素、所有元素相等。”

写代码之前先把不变量讲清楚，是区分"理解技术"和"背模板"最可靠的信号——面试官的反应非常一致。

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

下一篇预告

第三篇：链表操作里同样的快慢指针机制会换一种面孔出现——找中点、为归并排序对半切、k 个一组反转。对撞指针的思路也能直接迁移到链表回文判断。让一切顺起来的关键技巧是虚拟头节点——下一篇见。

LeetCode（二）—— 双指针技巧