双指针与滑动窗口

2.4 双指针与滑动窗口

本节摘要：双指针是"利用单调性省掉一次扫描"的集大成者。本节从有序数组的相向指针讲到盛水容器，再从定长窗口进化到可伸缩的滑动窗口，攻克无重复字符最长子串，总结"窗口何时扩、何时缩"的通用判定模式与常见错位。

有些问题，根本不用拆

本章前三节都在教怎么拆问题：递归拆、记忆化、搜索树。本节反过来：有些问题自带单调性——某个量增大时，另一个量的最优响应方向是确定的——这时不需要任何递归，两个指针按单调方向移动，一遍扫描完成优化。承上启下地说：双指针是策略进化的终点站，它教会我们的最后一课是"先看问题的结构，再决定用什么重型武器"，别上来就搬动态规划。

一、相向双指针：有序数组的老搭档

两数之和的第一章版本用哈希表；输入一旦有序，存在更优雅的解法：左指针指头、右指针指尾，两数之和偏大则右指针左移（变小），偏小则左指针右移（变大），命中即返回。每步至少淘汰一个元素，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 []

print(two_sum_sorted([2, 7, 11, 15, 18], 26))   # 输出 [2, 3]（11 加 15）
​

为什么敢一次淘汰一整列？因为有序：固定 nums[lo] 时，nums[hi] 配不上，比 nums[hi] 更小的那些虽然可能配上，但它们与更大左端的组合已在更早的步骤里被考虑过或必将被考虑——严格论证依赖不变式"答案若存在，始终处于两指针之间"。这个不变式论证是面试的必答题，说不出它，解法就只是背出来的。盛水容器是同款思想的进阶：左右指针夹住容器，移动短板那一侧（移动长板只会让宽度变小、高度不增，必然更差），同样一遍扫描。判断"移动哪边不亏"的单调性分析，是这类题的灵魂步骤。

二、同向双指针：快慢追赶

同向版本里两个指针速度不同但方向一致，第一章链表的快慢指针是它在链表上的化身；数组上最典型的应用是原地删除：把不重复（或不等于目标值）的元素搬到数组前段，慢指针标记已处理区的边界，快指针负责探路。空间 O(1)、时间 O(n)，数组还能保证前 k 位就是答案。

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

a = [0, 0, 1, 1, 1, 2, 2]
k = remove_duplicates(a)
print(k, a[:k])     # 输出 3 [0, 1, 2]
​

三、滑动窗口：会伸缩的区间

定长窗口好办：右指针每前进一格、左指针跟进一格。真正的进化是可伸缩窗口——右指针扩张探索，当窗口违反约束时左指针收缩恢复，窗口在"前进与回缩"之间波浪式推进。两个指针都只前进不后退，总移动次数各为 n，时间 O(n)。代表题：无重复字符的最长子串。

def length_of_longest_substring(s):
    last_seen = {}        # 字符到最近下标
    left = 0
    best = 0
    for right, ch in enumerate(s):
        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

print(length_of_longest_substring("abcabcbb"))   # 输出 3（abc）
print(length_of_longest_substring("bbbbb"))      # 输出 1（b）
print(length_of_longest_substring("pwwkew"))     # 输出 3（wke）
​

滑动窗口的伸缩节律

窗口题的常见错位有两个：一是左指针回缩时用 while 而不是 if——一次右扩可能引入多个违规，必须缩到彻底合规；二是窗口状态的更新顺序——先判断再纳入还是先纳入再判断，不同题不同，写错一个样例就露馅。调试窗口题的黄金手段是把每次扩张收缩时的左右界与窗口内容打印出来，肉眼核对几轮就能定位。

四、窗口变式：换计数对象的同款节律

滑动窗口的计数对象不止"字符是否重复"一种，同一套伸缩节律换个约束条件就是一道新题。最小覆盖子串：给字符串 s 与 t，求 s 中包含 t 全部字符的最短子串。窗口状态从"有无重复"换成"t 的字符还缺几个"，右指针扩张直到凑齐，左指针在凑齐状态下尽力收缩，每轮收缩后更新最短答案——扩张与收缩的条件对调，节律不变。长度不超过 k 且和最大的子数组则更直接：窗口和超限就收缩，扩张时顺便记最大窗口。

from collections import Counter

def min_window(s, t):
    need = Counter(t)
    missing = len(t)
    left = 0
    best = (float("inf"), 0, 0)
    for right, ch in enumerate(s, 1):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:                  # 已凑齐，尽力收缩
            if right - left < best[0]:
                best = (right - left, left, right)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return "" if best[0] == float("inf") else s[best[1]:best[2]]

print(min_window("ADOBECODEBANC", "ABC"))    # 输出 BANC
​

对照原始的无重复最长子串，可以总结出窗口题的通用骨架：窗口状态（计数字典或集合）、违反判定（缺还是多）、左指针收缩条件（恢复约束还是破坏约束）。三要素一换就是新题，骨架永不动摇。这也是为什么面试官喜欢在窗口题上连追三问——考察的就是你有没有把节律抽象出来，而不是背某一道题的代码。调试时打印每轮扩张收缩后的左右界与状态摘要，肉眼核对三五个回合，绝大多数窗口错位都能当场定位。

本节要点回顾

• 单调性是前提：先论证"某个量变化时最优响应方向确定"，才有资格上双指针；
• 相向指针靠不变式：答案始终在两指针之间，所以每步淘汰一侧是安全的；
• 盛水容器的决策：永远移动短板侧，移动长板侧必然不优；
• 可伸缩窗口节律：右扩探索、违反即左缩，两指针只进不退故线性；
• 收缩用 while、状态更新顺序要现场定：这两处是窗口题的高频错位。

本章策略链收官。下一章进入树形世界：递归思想将在二叉树遍历上正式亮相，堆、前缀树、并查集各自针对个具体瓶颈登场。