算法 2026-11-12 8 分钟

双指针:从有序数组到滑动窗口

SinleyCoooper 发布于 约 8 分钟阅读

第一次见到双指针是在两数之和的题解里。当时我把它当成模板背下来:一个 while (left < right),指针往里收,收完就出答案。后来题做多了才发现,「双指针」这个名字下面其实是三种不同的结构——对撞、快慢、滑动窗口。它们只共用一个前提:指针只会朝一个方向走,所以每个元素最多被访问常数次。

双指针不是技巧,是把「单调性」翻译成「每个元素只被访问常数次」。一旦这个性质不成立,模板就会退化成暴力枚举。

三种结构,一张表

把名字拆开看,区别只在两件事:指针怎么动,以及靠什么保证不漏解。整理成一张表更清楚:

三种双指针结构的对比
变体指针怎么动前提时间
对撞指针一左一右,向中间收区间有序,或两端信息足够排除一侧O(n)
快慢指针同向,步长不同(1 与 2)结构可迭代,状态有限O(n)
滑动窗口右端扩张,左端按需收缩窗口合法性随端点单调O(n)

对撞指针:用单调性排除

有序数组里的两数之和是最干净的例子。暴力是 O(n²),而双指针只需要 O(n),代价是必须有序——排序那一步已经把「谁比谁大」这个信息买下来了。

python
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),代价只是多走几圈。

  • 判环与找环入口:相遇后把慢指针放回头部,同速前进,再次相遇处即入口。
  • 找中点:快指针到尾时慢指针在中点,链表归并排序里反复用到。
  • 找重复数:把数组值当下标,问题立刻变成「链表判环」。

滑动窗口:把「连续」变成「前缀」

窗口题的关键不是模板,而是回答两个问题:右端扩张之后,窗口还合法吗?左端在什么条件下必须收缩?把这两个条件写死,代码几乎是机械的。

go
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 的计数,前缀和加单调队列更稳。
  • 要枚举所有解:双指针通常只给出一组或计数,全量枚举还是得回到搜索。

写算法题最省时间的做法,是先判断「这题有没有单调性」,再看用哪种指针。顺序反了,就会变成背模板、套不上的循环。