第 43 章　双指针与滑动窗口

本章配套 20 道例题，见 §例题。

双指针是用「单调性」把 \(O(n^2)\) 的二重循环压成 \(O(n)\) 的技巧。 它的核心不是「两个变量」，而是这句话：

右端点右移时，左端点只会右移、绝不会左移。

有了这条单调性，两个指针各自最多走 \(n\) 步，总步数 \(\le 2n\)，所以是 \(O(n)\)—— 哪怕代码里有嵌套的 while。「有嵌套循环 ≠ 复杂度是平方」，这是双指针最反直觉的地方。

---

1　三种双指针

类型	指针走向	典型问题
同向双指针（尺取法）	都从左往右	最长/最短满足条件的子段
对撞指针	一左一右往中间	有序数组两数之和、回文判定、田忌赛马
快慢指针	同向不同速	链表找环 / 找中点

第三种见 链表，本章讲前两种。

---

2　同向双指针的通用框架

背下这个骨架，90% 的滑窗题都是往里填三行。

l = 0                              # 窗口左端，闭区间 [l, r]
best = 0
# state = ...                      # 窗口内的统计量：和 / 计数器 / 不同元素数 ...
for r in range(n):
    # 1) 把 a[r] 加入窗口，更新 state
    add(a[r])

    # 2) 只要窗口非法，就收缩左端。l 只增不减：r 变大后，更靠左的左端只会更非法
    while not ok(state):
        remove(a[l])
        l += 1

    # 3) 循环不变量：每轮结束时 [l, r] 合法，且 l 是使它合法的最小值
    best = max(best, r - l + 1)

# 均摊 O(n) 的理由：r 走 n 步，l 至多也走 n 步且从不回退，内层 while 的总执行次数 <= n。
# 所以「嵌套 while」并不意味着平方复杂度——前提是 add / remove 都是 O(1)

三条使用要点：

要点	说明
while 而不是 if	加入一个元素可能要弹掉多个
add / remove 必须 \(O(1)\)	否则总复杂度不是 \(O(n)\)
循环不变量	每轮结束时 [l, r] 都是合法的

求「最短」而不是「最长」时，收缩条件要反过来

l = 0
best = INF
for r in range(n):
    add(a[r])
    while ok(state):               # 只要还合法就继续缩，找最短
        best = min(best, r - l + 1)    # 在缩之前记录：此刻 [l, r] 还是合法的
        remove(a[l])
        l += 1                     # 缩到刚好破坏合法性为止，下一轮再靠 r 补回来

「最长」在 while 外统计，「最短」在 while 内统计。 这一条写反是滑窗题最高频的 WA。

什么时候双指针是错的

双指针成立的前提是单调性：

• 求最长：窗口合法 ⟹ 它的任意子区间也合法（合法性对收缩封闭）；
• 求最短：窗口非法 ⟹ 它的任意子区间也非法。

典型的反例是「子段和恰好为 \(k\)，但数组里有负数」——加入元素时和不再单调递增， 右端右移后左端可能需要回退。这类题必须改用前缀和 + 哈希表，见 前缀和与差分 §5。

数组元素	「和 \(\le k\) 的最长子段」
全为正	✅ 双指针 \(O(n)\)
含 0	✅ 仍然可以（和不减）
含负数	❌ 双指针失效，改用前缀和 + 单调队列 / 哈希

---

3　对撞指针

两个指针从两端往中间走，每一步至少排除一个候选，所以也是 \(O(n)\)。

# 有序数组里找和为 target 的一对
l, r = 0, n - 1                    # 一左一右，候选是所有满足 l < r 的下标对
while l < r:                       # 相遇即停：l == r 时只剩一个元素，配不成对
    s = a[l] + a[r]
    if s == target:
        break
    if s < target:
        l += 1                     # 和太小 -> a[l] 与更小的右端配只会更小，整列淘汰，只能增大左端
    else:
        r -= 1                     # 和太大 -> a[r] 与更大的左端配只会更大，整列淘汰，只能减小右端
# 每一步至少淘汰一行或一列候选，两个指针合计最多走 n 步，所以是 O(n)

对撞指针几乎总是要先排序，因为它靠的是「往左变小、往右变大」这个单调性。 田忌赛马式的贪心（最快的对最快的，跑不过就用最慢的去消耗）也是对撞指针的应用，见 贪心。

---

4　单调队列：滑动窗口最值

滑窗最值不能用前缀和（max 没有逆运算），也不必上线段树——单调队列是 \(O(n)\) 的最优解。

思想：队列里存下标，对应的值单调递减。若新元素比队尾大，队尾那些元素 「既比新元素小、又比新元素早过期」，永无出头之日，直接弹掉。

from collections import deque


def sliding_max(a, k):
    """长度为 k 的滑动窗口最大值，返回 n-k+1 个结果，O(n)。"""
    dq = deque()                    # 存下标，对应值单调递减，a[dq[0]] 是当前窗口最大值
    res = []
    for i, v in enumerate(a):
        # 队尾那些元素既比 v 小、又比 v 先过期，此后永远当不上最大值，可以永久丢弃
        while dq and a[dq[-1]] <= v:      # 队尾比新元素小 -> 永远轮不到它
            dq.pop()
        dq.append(i)                      # 入队后，队列里的值仍保持单调递减
        if dq[0] <= i - k:                # 窗口是 [i-k+1, i]，下标 <= i-k 的已经出界
            dq.popleft()
        if i >= k - 1:                    # 前 k-1 步窗口还没填满，不输出
            res.append(a[dq[0]])
    # 每个下标最多入队一次、出队一次，总操作 <= 2n，所以整体是均摊 O(n)
    return res

求最小值只需把 <= 改成 >=。四个必须记牢的细节：

细节	原因
队列里存下标不存值	判断过期要靠下标
弹队尾用 while 不用 if	一次可能弹掉多个
<= 还是 <	用 <= 弹掉等值元素，队列更短；用 < 也对但会留冗余
必须用 deque	list.pop(0) 是 \(O(n)\)，会退化成 \(O(n^2)\)

collections.deque 的两端操作是 \(O(1)\)，随机访问 dq[i] 是 \(O(n)\)。 单调队列只访问 dq[0] 和 dq[-1]，这两个是特化过的 \(O(1)\)，放心用。 见 队列与双端队列。

单调队列与单调栈的对照、以及它在 DP 优化里的用法，见 单调队列 与 DP优化。

---

5　窗口内「状态」的四种维护方式

滑窗题的难点从来不是指针，而是如何 \(O(1)\) 地维护窗口状态。

要维护的量	数据结构	加入 / 删除
区间和	一个变量	s += x / s -= x
每个值出现次数	Counter / list 桶	cnt[x] += 1 / -= 1
不同元素个数	Counter + 计数器	计数从 0→1 时 distinct += 1
区间最值	单调队列	见 §4

第三种的标准写法（这是「最多 \(k\) 种不同元素的最长子段」类题的核心）：

from collections import Counter

cnt = Counter()                    # 窗口内每个值的出现次数
distinct = 0                       # 窗口内不同值的个数
l = 0
for r in range(n):
    if cnt[a[r]] == 0:             # 计数由 0 变 1 的那一刻，才是「新增一种」
        distinct += 1              # 新出现的值
    cnt[a[r]] += 1
    while distinct > k:            # 种类超标，收缩左端直到合法
        cnt[a[l]] -= 1
        if cnt[a[l]] == 0:         # 计数由 1 变 0 的那一刻，才是「少了一种」
            distinct -= 1          # 这个值彻底离开窗口
        l += 1

---

6　例题

题号	题名	难度	题解
BISHI114	【模板】滑动窗口	简单	题解
BISHI115	可匹配子段计数	简单	题解
BISHI116	【模板】双指针	中等	题解
BISHI117	小苯的IDE括号问题（easy）	中等	题解
BISHI118	相差不超过k的最多数	中等	题解
BISHI119	小红的01子序列构造（easy）	中等	题解
BISHI120	？？？	较难	题解
BM54	三数之和	中等	题解
BM87	合并两个有序的数组	简单	题解
BM90	最小覆盖子串	较难	题解
BM92	最长无重复子数组	中等	题解
BM93	盛水最多的容器	中等	题解
LC15	三数之和	中等	题解
LC76	最小覆盖子串	困难	题解
LC3	无重复字符的最长子串	中等	题解
LC11	盛最多水的容器	中等	题解
LC75	颜色分类	中等	题解
LC283	移动零	简单	题解
LC287	寻找重复数	中等	题解
LC438	找到字符串中所有字母异位词	中等	题解

BISHI114　【模板】滑动窗口（简单）

\(n \le 2\times10^5\)，窗口大小 \(k\)，输出每个窗口的最大值。 题面见 原题。

单调队列的裸模板：

import sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    a = list(map(int, data[2:2 + n]))

    dq = deque()                          # 存下标，对应值单调递减；队首即当前窗口最大值
    out = []
    ap = out.append
    for i in range(n):
        v = a[i]
        # 队尾元素比 v 小且比 v 先过期，永远没有出头之日，直接丢弃
        while dq and a[dq[-1]] <= v:      # 队尾比新元素小的都没用了
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                # 当前窗口是 [i-k+1, i]，下标 <= i-k 的已过期
            dq.popleft()
        if i >= k - 1:                    # 窗口首次填满是在 i == k-1，从这里开始输出
            ap(a[dq[0]])
    # 每个下标入队、出队各至多一次，总代价 O(n)
    sys.stdout.write(" ".join(map(str, out)) + "\n")


main()

• 样例 2（\(k=1\)）：每次新元素进来会把队尾全弹光，答案就是原数组，逻辑自洽。
• 样例 3（\(k=n\)）：只输出一个全局最大值，说明 i >= k-1 的判断不能写成 i >= k。
• 不要用 list 当队列：pop(0) 是 \(O(n)\)，\(2\times10^5\) 时直接退化。

若题目要的是「每个窗口的最大值和最小值」，开两个 deque 分别维护， 不要试图用一个队列同时管两头。

BISHI115　可匹配子段计数（简单）

数组 \(a\)（长 \(n\)）、\(b\)（长 \(m\)），对 \(a\) 的每个长度恰为 \(m\) 的连续子段 \(c\)， 定义匹配度 \(\operatorname{match}(c) = \sum_x \min(cnt_x(c), cnt_x(b))\)， 求 \(\operatorname{match} \ge k\) 的子段数。多组数据，\(\sum n, \sum m \le 2\times10^5\)。 题面见 原题。

定长窗口 + 增量维护匹配度。关键是想清楚 \(\min(cnt_x(c), cnt_x(b))\) 怎么增量更新：

• 加入元素 \(x\) 时：若加入前 \(cnt_x(c) < cnt_x(b)\)，说明这个 \(x\) 还「有位置可占」， 匹配度 \(+1\)；否则是多余的，匹配度不变。
• 删除元素 \(y\) 时：先减 cnt，若减完后 \(cnt_y(c) < cnt_y(b)\)，说明刚才那个 \(y\) 是「占着位置的」，匹配度 \(-1\)。

import sys
from collections import Counter


def main():
    data = sys.stdin.buffer.read().split()
    p = 0
    t = int(data[p]); p += 1
    out = []
    for _ in range(t):
        n = int(data[p]); m = int(data[p + 1]); k = int(data[p + 2]); p += 3
        a = list(map(int, data[p:p + n])); p += n
        b = list(map(int, data[p:p + m])); p += m

        need = Counter(b)                 # b 里每个值的需求量
        cur = Counter()                   # 当前窗口里每个值的数量
        match = 0                         # 窗口与 b 的多重集合交的大小
        ans = 0
        for i in range(n):
            x = a[i]
            # 加入前 cur[x] < need[x] 说明 x 还有空位可占，min 会跟着 +1；否则是多余的
            if cur[x] < need[x]:          # 这个 x 能占住一个位置
                match += 1
            cur[x] += 1
            if i >= m:                    # 窗口长度固定为 m，多出一个就弹左端
                y = a[i - m]
                cur[y] -= 1
                # 减完仍 < need[y]，说明刚弹掉的那个 y 原本是占着位置的，min 要跟着 -1
                if cur[y] < need[y]:      # 弹掉的是「占位」的那个
                    match -= 1
            if i >= m - 1 and match >= k:    # 窗口填满（i >= m-1）后才是合法子段
                ans += 1
        out.append(ans)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

三个要点：

• 「重排后至少 \(k\) 个位置相等」= 多重集合的交的大小，题面已经把它形式化成 \(\sum_x \min(cnt_x(c), cnt_x(b))\)，这一步想不通整题就废了。
• \(a_i \le 10^6\) 但 \(\sum n \le 2\times10^5\)：值域比元素数大得多， 所以用 Counter 而不是 list 桶（否则每组数据都要清空一个 \(10^6\) 的数组， 多组下直接 TLE）。这是 桶计数与离散化 讲的选型问题。
• 多组数据的 Counter 必须每组新建，绝不能复用后 clear() 之外的写法。

BISHI116　【模板】双指针（中等）

\(n \le 2\times10^5\)，\(0 \le a_i \le n\)。求所有最长的、元素两两不同的区间， 按 \(l\) 递增输出。 题面见 原题。

这是 §2 框架的直接应用，但多了一个「输出全部最优解」的要求。

关键洞察：对每个右端点 \(r\)，「以 \(r\) 结尾且元素互不相同」的最长区间是唯一的， 记作 \([l_r, r]\)。所有的最长区间必然都是这种形式，所以只需要在扫描过程中 把长度等于最大值的 \([l_r, r]\) 全部收集起来。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))

    last = [-1] * (n + 1)        # 值 -> 上一次出现的下标（题目保证 0 <= a_i <= n），-1 表示没出现过
    best = 0
    l = 0                        # 窗口左端；不变量：[l, r] 内元素两两不同
    segs = []
    for r in range(n):
        v = a[r]
        # 只有当上一次出现位置落在窗口内时才需要收缩；写成 l = last[v] + 1 会让 l 回退，破坏单调性
        if last[v] >= l:
            l = last[v] + 1      # 左端跳到上一次出现位置的右边
        last[v] = r
        length = r - l + 1       # 以 r 结尾的、元素互不相同的最长区间长度
        if length > best:
            best = length
            segs = [(l, r)]      # 出现更长的，之前收集的全作废
        elif length == best:
            segs.append((l, r))  # 并列最长，一起收好；l 随 r 单调不减，天然按 l 递增
    out = [str(len(segs))]
    out.extend("%d %d" % (l + 1, r + 1) for l, r in segs)
    sys.stdout.write("\n".join(out) + "\n")


main()

四个要点：

• l = max(l, last[v] + 1) 而不是 l = last[v] + 1： 代码里写成 if last[v] >= l 是同一件事。少了这个判断，遇到 「重复元素在窗口左边之外」时左端会回退，单调性被破坏，答案直接错。
• 值域 \([0, n]\) 用 list 桶存 last，比 dict 快 2–3 倍；数组要开 \(n+1\) 长。
• 收集全部最优解：> 时清空重来，== 时追加。因为 \(l\) 随 \(r\) 单调不减， 收集顺序天然满足题目要求的「\(l\) 递增」，不用再排序。
• 题目明说没有 SPJ，所以输出顺序必须严格按 \(l\) 递增——这里靠单调性白拿。

BISHI117　小苯的 IDE 括号问题（easy）（中等）

括号串里有一个光标 I，执行 \(k\) 次 backspace / delete，输出最终串。 backspace：若光标左边是 ( 且右边是 )，一次删掉这对；否则删左边一个字符。 delete：删右边一个字符。\(n, k \le 2\times10^5\)。 题面见 原题。

光标问题的标准模型：两个栈（对顶栈）。光标左边的字符存在 left 栈里（栈顶靠近光标）， 右边的字符倒序存在 right 栈里（栈顶也靠近光标）。这样两种删除都是 \(O(1)\)：

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    s = data[2].decode()
    i = s.index("I")                      # 光标位置，s[i] 是那个 'I'
    left = list(s[:i])                    # 光标左侧，栈顶（末尾）最靠近光标
    right = list(s[i + 1:][::-1])         # 光标右侧倒序存，栈顶也最靠近光标

    for j in range(3, 3 + k):             # 前 3 个 token 是 n、k、s，操作从下标 3 开始
        op = data[j]
        if op == b"delete":
            if right:                     # 右侧为空时该操作无效果
                right.pop()               # 两个栈的栈顶都紧贴光标，删除因此是 O(1)
        else:                             # backspace
            # 光标左边是 '(' 且右边是 ')' 时优先成对删除，这一分支必须排在普通删除之前
            if left and left[-1] == "(" and right and right[-1] == ")":
                left.pop()                # 成对删除
                right.pop()
            elif left:                    # 否则退化成删左边一个字符；左侧为空则无效果
                left.pop()
    sys.stdout.write("".join(left) + "I" + "".join(reversed(right)) + "\n")


main()

• right 必须倒序存，否则删「右边第一个字符」是 list.pop(0)，\(O(n)\) 退化。 这正是「用两个栈模拟光标」这一模型存在的理由。
• 两种删除都要判空（「若左侧为空则无效果」）。
• 最终输出别忘了把 I 放回去，且 right 要再倒回来。

这题的标签是「双指针」，但更准确的说法是对顶栈—— 它和双指针共享同一个直觉：两个方向各自维护，中间是分界线。 相关模型见 栈。

BISHI118　相差不超过 k 的最多数（中等）

排序后双指针求最长合法段，是 §2 框架最纯粹的实例。 完整代码与「为什么排序等价于最轻量的离散化」的讨论见 桶计数与离散化 §6。

BISHI119　小红的 01 子序列构造（easy）（中等）

01 串 \(s\)（\(n \le 2\times10^5\)），求任意一个区间 \([l, r]\)， 使子串里恰好有 \(k\ (k \le 10^{10})\) 个 01 子序列；无解输出 \(-1\)。 题面见 原题。

单调性分析：记 \(f(l, r)\) 为窗口内 01 子序列个数。

• 固定 \(l\)，\(r\) 增大时 \(f\) 单调不减（每个新的 1 会带来「它左边 0 的个数」个新对）；
• 固定 \(r\)，\(l\) 增大时 \(f\) 单调不增。

于是：对每个 \(l\)，找最小的 \(r\) 使 \(f \ge k\)；若此时恰好 \(f = k\) 就是答案， 否则这个 \(l\) 一定无解（\(f\) 从 \(< k\) 一步跨过了 \(k\)）。由于最小的 \(r\) 随 \(l\) 单调不减， 两个指针各走一遍，总复杂度 \(O(n)\)。

增量维护是本题的技术核心：

• 右端加入 0：zeros += 1；加入 1：cnt += zeros。
• 左端弹出 0：zeros -= 1，然后 cnt -= 窗口内 1 的个数 （这个 0 与它右边的每个 1 各构成一对）。窗口内 1 的个数 \(=\) 窗口长度 \(-\) zeros，不用另外维护。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    s = data[2]

    r = 0            # 窗口是左闭右开 [l, r)，r 从不回退
    zeros = 0        # 窗口内 0 的个数
    cnt = 0          # 窗口内 "01" 子序列个数
    for l in range(n):
        # 固定 l 时 cnt 随 r 单调不减，所以一路右推到首次 cnt >= k 就停
        while r < n and cnt < k:
            if s[r] == 48:            # 字符 '0' 的 ASCII 码
                zeros += 1
            else:                     # '1'：与前面每个 0 各配成一对
                cnt += zeros
            r += 1
        if cnt == k:
            print(l + 1, r)           # 输出 1-indexed 闭区间：左端 l+1，右端就是开区间的 r
            return
        # 这里 cnt 要么 > k（一步跨过去了）要么 < k（串已扫完），本 l 无解，左端右移
        if s[l] == 48:                # 只有 0 离开窗口才会减少对数
            zeros -= 1
            cnt -= (r - l - 1) - zeros    # 窗口 [l+1, r) 的长度减去其中 0 的个数 = 1 的个数
    # l、r 各自单调右移，各走至多 n 步，总复杂度 O(n)
    print(-1)


main()

本题是 special judge（「输出任意一组均可」），本地按样例逐字符比对能过 只是因为这份贪心恰好先找到样例给出的那组解。 提交到 OJ 时不必担心，但自测时别因为输出和样例不同就以为写错了，见 输入输出处理 的 special judge 一节。

\(k\) 最大 \(10^{10}\)，超过 32 位——C++ 要 long long，Python 无所谓。

BISHI120　？？？（较难）

串 \(s\) 含小写字母与 ?，把每个 ? 替换成小写字母，使 \(t\) 成为 \(s\) 的子序列； 输出任意方案或报告无解。\(\sum|s| \le 2\times10^5\)。 题面见 原题。

贪心 + 同向双指针：\(i\) 扫 \(s\)，\(j\) 指向 \(t\) 中待匹配的字符。 只要当前位能匹配（字符相同，或者是 ?）就立刻匹配——越早匹配越好， 因为把匹配位置尽量左移，留给后面的空间最大（这是子序列匹配的标准交换论证）。

# [片段] 本题为 special judge（答案不唯一），此处只给核心逻辑
j = 0                                 # j 指向 t 中下一个待匹配的字符
res = list(s)
for i, ch in enumerate(s):
    # 匹配位置尽量左移，给后面的字符留出最多的空间（子序列匹配的标准交换论证）
    if j < len(t) and (ch == t[j] or ch == "?"):
        res[i] = t[j]                 # 能匹配就立刻匹配
        j += 1
    elif ch == "?":
        res[i] = "a"                  # t 已匹配完或本位对不上，剩下的问号必须填成具体字母
print("YES" if j == len(t) else "NO")   # 扫完 s 后 j < len(t) 是唯一的无解情形

• 贪心正确性：若存在任何合法方案，那么「每一步都取最左可匹配位置」的方案也合法—— 逐位把方案中的匹配位置左移，不会破坏后续的可行性。
• 无解判定只有一条：扫完 \(s\) 后 \(j < |t|\)。
• 注意还没轮到匹配的 ?（\(j\) 已经用完）也要填上一个具体字母，不能留 ?。

本题的题解文件尚未建立，上面只是思路与核心片段，未经样例实测。

---

面试题单里的七道双指针题

按 §1 的分类摆开，这七道题正好把「同向」与「对撞」两类各填满一半。

对撞指针（§3）。 盛水最多的容器是这一类最干净的形态：两端各一个指针， 面积由较矮的那一侧决定，所以每次移动矮的那边—— 移动高的那边只会让宽度变小而高度不变，答案不可能更优。 这句「移动高的一侧不可能更优」就是它的正确性证明，一句话的交换论证。

三数之和（同一道题在另一处题库里编号 LC 15. 三数之和）先排序， 再固定第一个数、在其右侧用对撞指针找配对，\(O(n^2)\)。 它真正的难点在去重：三个位置都要跳过与前一个相同的值， 且跳过的时机不同——第一个数在进入内层循环前跳， 另外两个数在找到一组答案之后跳。漏掉任何一处都会输出重复三元组。

合并两个有序的数组是对撞的变体：题目要求原地合并进第一个数组， 所以要从后往前填，两个指针分别从两段的末尾出发，谁大先放到尾部。 从前往后填会覆盖掉还没读到的元素。

同向双指针（§2 的骨架直接套）。 最长无重复子数组的 state 是「窗口内每个值出现的次数」， ok(state) 是「没有任何值出现两次以上」，往骨架里填三行即可。 更快的写法是记「每个值上一次出现的下标」，左端直接跳到那个下标的下一位， 省掉逐个收缩的循环——两种写法同阶，后者常数更小。

最小覆盖子串（同一道题在另一处题库里编号 LC 76. 最小覆盖子串）是同向双指针里最值得练的一道： 求最短的、包含目标串全部字符（含重数）的子串。 state 是一个计数器加一个整数 missing（还差几个字符）， 用 missing 而不是每次比对整张计数表，是这题从 \(O(n \times \Sigma)\) 降到 \(O(n)\) 的关键。 注意求的是最短窗口，所以答案要在「收缩到刚好非法之前」结算， 与 §2 骨架里求最长时的结算位置正好相反。

另一处题库里的六道双指针题

LC 283. 移动零与 LC 75. 颜色分类：同向双指针做原地划分。 LC283 维护一个「已确定的非零前缀末尾」，扫到非零就与该位置交换并前移， 一遍 \(O(n)\)、额外空间 \(O(1)\)，且非零元素的相对次序不变。 LC75 颜色分类把这一招用两次：三个指针把数组切成「\(0\) 区 / \(1\) 区 / 未处理 / \(2\) 区」四段， 扫到 \(0\) 与 \(0\) 区末尾换、扫到 \(2\) 与 \(2\) 区首端换。 换到 \(2\) 之后当前下标不能前进——换过来的值还没检查过；换到 \(0\) 之后则可以前进， 因为从左边换过来的一定是已经判过的 \(1\)。这一处不对称是本题唯一的坑。

LC 11. 盛最多水的容器：相向双指针，每一步都要说清「排除掉的那一批为什么不可能更优」。 面积由较矮的一侧与宽度决定，所以移动较高的一侧只会让宽度变小、高度不增， 以当前较矮一侧为边界的所有方案就此全部出局，可以安全丢弃。 两指针合计走 \(n\) 步，\(O(n)\)。 这条论证是相向双指针的通用形态：没有它，双指针就只是一个没有依据的贪心。

LC 3. 无重复字符的最长子串与 LC 438. 找到字符串中所有字母异位词：可变窗口与定长窗口。 LC3 用一个哈希表记「每个字符最近一次出现的位置」， 右端点每前进一步，左端点就跳到「重复字符上次位置的下一格」与当前左端点的较大者， 两个指针都只前进不后退，\(O(n)\)。 LC438 的窗口长度固定为模式串长度，只需比较两个长为 26 的计数数组； 每次滑动做两次 \(O(1)\) 的增减，再配一个「还有几个字符的计数没对上」的计数器， 整体 \(O(n)\)，比每次重比 26 个格子省一个常数倍。

LC 287. 寻找重复数：快慢指针跑在「下标→值」构成的函数图上。 数组长 \(n + 1\)、取值都在 \([1, n]\) 内，把 i -> a[i] 看成一条边， 从 \(0\) 出发必然走进一个环，而环的入口正是那个重复的数——只有它有两条入边。 于是这题与链表找环入口是同一份代码：先让快慢指针相遇，再把一个指针放回起点同步单步走。 \(O(n)\) 时间、\(O(1)\) 空间，且不修改数组。 排序或开计数数组都更直白，但前者破坏输入、后者要 \(O(n)\) 额外空间，题面把这两条都堵死了。

7　本章速查

场景	做法
最长满足条件的子段	同向双指针，best 在 while 外更新
最短满足条件的子段	同向双指针，best 在 while 内更新
有序数组两数之和	对撞指针
滑动窗口最值	单调队列，\(O(n)\)
窗口内不同元素数	Counter + 计数从 0→1 / 1→0 时增减
光标 / 中间插入删除	对顶栈（两个 list，一个倒序）
数组含负数求「和 \(\le k\)」	❌ 双指针失效，改前缀和 + 哈希
队列容器	必须 deque，list.pop(0) 是 \(O(n)\)

单调队列细节	值
队列存什么	下标（要靠它判过期）
求最大值	队列值单调递减，弹队尾用 <=
求最小值	队列值单调递增，弹队尾用 >=
队首过期判断	dq[0] <= i - k
开始输出	i >= k - 1

模板	位置
同向双指针（最长 / 最短）	§2
对撞指针	§3
单调队列	§4
窗口内不同元素计数	§5