第一次见到双指针是在两数之和的题解里。当时我把它当成模板背下来:一个 while (left < right),指针往里收,收完就出答案。后来题做多了才发现,「双指针」这个名字下面其实是三种不同的结构——对撞、快慢、滑动窗口。它们只共用一个前提:指针只会朝一个方向走,所以每个元素最多被访问常数次。
双指针不是技巧,是把「单调性」翻译成「每个元素只被访问常数次」。一旦这个性质不成立,模板就会退化成暴力枚举。
三种结构,一张表
把名字拆开看,区别只在两件事:指针怎么动,以及靠什么保证不漏解。整理成一张表更清楚:
| 变体 | 指针怎么动 | 前提 | 时间 |
|---|---|---|---|
| 对撞指针 | 一左一右,向中间收 | 区间有序,或两端信息足够排除一侧 | O(n) |
| 快慢指针 | 同向,步长不同(1 与 2) | 结构可迭代,状态有限 | O(n) |
| 滑动窗口 | 右端扩张,左端按需收缩 | 窗口合法性随端点单调 | O(n) |
对撞指针:用单调性排除
有序数组里的两数之和是最干净的例子。暴力是 O(n²),而双指针只需要 O(n),代价是必须有序——排序那一步已经把「谁比谁大」这个信息买下来了。
def two_sum_sorted(nums, target):
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
return (lo, hi)
if s < target:
lo += 1 # 和太小:只能让最小的一端变大
else:
hi -= 1 # 和太大:只能让最大的一端变小
return None
不变量:被排除的候选集不会再回来
为什么不会漏解?当 nums[lo] + nums[hi] < target 时,任何以 lo 为左端、右端不超过 hi 的组合都只会更小,于是整批候选被一次性排除。每一步都排除一批,指针才不会回头。
快慢指针:步差就是追及速度
快慢指针常被当成「找中点」的小技巧,但它真正好用的是判环:快指针每轮多走一步,两者距离每轮缩短 1,进入环后必然相遇,不需要额外的 visited 集合。空间从 O(n) 降到 O(1),代价只是多走几圈。
- 判环与找环入口:相遇后把慢指针放回头部,同速前进,再次相遇处即入口。
- 找中点:快指针到尾时慢指针在中点,链表归并排序里反复用到。
- 找重复数:把数组值当下标,问题立刻变成「链表判环」。
滑动窗口:把「连续」变成「前缀」
窗口题的关键不是模板,而是回答两个问题:右端扩张之后,窗口还合法吗?左端在什么条件下必须收缩?把这两个条件写死,代码几乎是机械的。
func lengthOfLongestSubstring(s string) int {
last := make(map[byte]int, len(s))
best, left := 0, 0
for right := 0; right < len(s); right++ {
if i, ok := last[s[right]]; ok && i >= left {
left = i + 1 // 窗口内出现重复,左端跳到重复字符之后
}
last[s[right]] = right
if right-left+1 > best {
best = right - left + 1
}
}
return best
}
注意 left 只增不减,所以内层虽然有 if,总执行次数仍然不超过 n,整体是线性的。窗口题写错,八成是把「左端可能回退」偷偷写了进去。
什么时候不该用
三种结构都依赖单调性,一旦这个前提不成立,就不该硬套:
- 要返回原下标:数组无序又不能排序时,用哈希表,别为了双指针破坏下标。
- 窗口性质不单调:含负数的最长子数组、和恰好为 k 的计数,前缀和加单调队列更稳。
- 要枚举所有解:双指针通常只给出一组或计数,全量枚举还是得回到搜索。
写算法题最省时间的做法,是先判断「这题有没有单调性」,再看用哪种指针。顺序反了,就会变成背模板、套不上的循环。