Algorithm · Sliding Window
同向双指针的收缩艺术：模板三件套 · 定长/可变/计数三类 · 从无重复子串到最小覆盖子串
右指针扩张、左指针收缩、窗口内维护统计——O(n) 的秘密是各走一遍
定长窗口 · 可变窗口（求最长/最短）· 计数窗口（频次/异位词）
窗口扩大/缩小时答案性质单调变化——否则只能 O(n²) 暴力
Expand · Shrink · Maintain
// 可变窗口万能骨架 func window(s string) { need := map[byte]int{} // 窗口统计 l := 0 for r := 0; r < len(s); r++ { // 1. 扩张：s[r] 进窗 need[s[r]]++ // 2. 收缩：不满足时缩左 for 窗口不合法(need) { need[s[l]]-- l++ } // 3. 此刻 [l,r] 合法，更新答案 ans = max(ans, r-l+1) } } // 求最短：合法时收缩，收缩完更新 ans
右指针无条件前进（探索）；左指针按合法性收缩（修复）；窗口统计（哈希/计数/位掩码）O(1) 维护窗口内信息。求最长=不合法时收缩；求最短=合法时收缩——只有第 2 步的 while 条件和第 3 步的更新时机互换。
l 和 r 都只前进不后退：r 走 n 步、l 最多走 n 步 → 总操作 ≤ 2n。这是摊还分析（复杂度 deck）——每个元素最多"进窗一次、出窗一次"。
窗口合法性不单调：右扩可能先变好又变坏再变好——收缩无法一步到位。此时回退 O(n²) 或换前缀和+哈希（560 求和类）。
字符频次 map（子串族）、和变量（定长和）、位掩码（小写字母可用 int32 优化成 O(1)）——统计结构要支持"进出各 O(1)"。
Fixed · Variable · Counting
滑动时一进一出、减去左端加右端。代表：1456 定长子串中元音最大数、438 找所有字母异位词（定长计数窗口，窗口频次 == 目标频次即命中）。
不合法就收缩、合法时记长度。代表：3 无重复字符最长子串（频次 >1 不合法）、209 长度最小的子数组（和 ≥ target 合法，求最短——合法时收缩更新）。
维护"已满足的字符种类数" vs 目标。76 最小覆盖子串：need 表 + match 计数，全部满足时收缩左端找最短——窗口模板的天花板题。
定长：r−l+1 > k 时 l++；求最长：while 不合法 l++；求最短：while 合法 l++。while 的条件就是题意的镜像，写窗口题先翻译这句话。
| 类型 | 收缩条件 | 更新时机 |
|---|---|---|
| 定长 | 长度超 k → l++ | 每步（长度==k 时） |
| 求最长 | 不合法 → l++ | while 之后（[l,r] 合法） |
| 求最短 | 合法 → l++ | while 之中/之后（记录最小） |
| 计数命中 | 长度超 len(p) → l++ | 频次相等时记下标 |
LC 3 · LC 76 · LC 209
// LC 3 无重复字符最长子串 func lengthOfLongestSubstring(s string) int { cnt := map[byte]int{} l, ans := 0, 0 for r := 0; r < len(s); r++ { cnt[s[r]]++ // 扩张 for cnt[s[r]] > 1 { // 重复→不合法 cnt[s[l]]-- // 收缩到去重 l++ } if r-l+1 > ans { ans = r - l + 1 // 合法时更新 } } return ans } // LC 76 最小覆盖子串：need + match // need[t] 目标频次；window 匹配一格 match++ // match == len(need) → 全覆盖，收缩左端 // 更新最短答案，直到不合法继续扩张
新进的 s[r] 计数 >1 就是唯一冲突源 → while 只需把左端缩到"这个字符只出现一次"。收缩结束后 [l,r] 无重复。判定 O(1)、收缩摊还 O(n)。
不能每次比对两个 map（O(26) 也行但丑）——用 match 计数："窗口内频次达到 need 的字符种类数"。match==len(need) 即覆盖，收缩时 match--。
和 ≥ target 合法 → 合法时收缩记最短。依赖"元素全正"（和随窗口单调）——有负数时失效，要换前缀和+单调队列（ LC 862）。
3 是求最长、209 是求最短、76 是计数覆盖——三类窗口各一。其余 90% 的窗口题是它们的变装（把"字符"换成"数字/元音/种类"）。
LC 3 · Visualized
Which Tool For Which Subarray
适合：合法性随窗口滑动单调变化（元素全正、约束可满足性单调）。求最长/最短连续段。失效场景：数组含负数（和不再单调）。
适合：精确和/计数匹配（和恰为 K、0/1 平衡）。560 和为 K：窗口做不了（有负数），pre[j]−pre[i]=K 计数即可。数组 deck 的前缀和段。
适合：窗口内最值（滑动窗口最大值 239）。合法性单调但要求的不是"存在"而是"最值"——窗口 + 单调队列 组合。
问"是否存在子数组"→ 先看单调：单调走窗口；不单调但和可累加 → 前缀和+哈希；问"窗口最值" → 单调队列；问"所有方案" → 回溯。连续子数组家族四大件各管一摊。
| 题目特征 | 工具 | 复杂度 |
|---|---|---|
| 最长无重复子串（3） | 滑动窗口 | O(n) |
| 和 ≥ target 最短（209，全正） | 滑动窗口 | O(n) |
| 和恰为 K（560，有负数） | 前缀和+哈希 | O(n) |
| 窗口最大值（239） | 单调队列 | O(n) |
| 最短超和（862，有负数） | 前缀和+单调栈 | O(n) |
| 异位词定位（438） | 定长计数窗口 | O(n) |
LeetCode Shortlist
| 变装 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 无重复 | 3 无重复最长子串 M · 159 至多两个不同字符 M · 340 至多 K 个不同 H | 159/340 是 3 的参数化（至多 k 种） |
| 至多转换 | 424 替换后的最长重复 M · 1004 最大连续1的个数 M | "至多 k 次操作"= 窗口内坏元素 ≤k |
| 求最短 | 209 长度最小子数组 M · 76 最小覆盖子串 H | 合法时收缩；76 加 match 计数 |
| 定长计数 | 438 异位词 E · 567 排列字符串 M · 1456 定长子串元音 M | 窗口频次 == 目标频次 |
| 组合技 | 239 滑动窗口最大值 H · 480 中位数 H | 窗口 + 单调队列/双堆（堆 deck） |
Interview QA
l 与 r 都单调前进：r 走 n 步、l 总共 ≤ n 步 → 总操作 ≤ 2n。这是摊还论证（每个元素最多进窗一次出窗一次），不是"每步 O(1)"的误会。
窗口变大不会让"非法变合法"（求最长时）或反之（求最短时）。209 靠"全正数"保证；LC 3 靠"去掉左端重复即可恢复"。不单调 → 窗口失效。
求最长：不合法才 while 收缩、之后更新；求最短：合法就 while 收缩、收缩中/后更新。两处互换，其余骨架相同。
判断"窗口覆盖 t"若每次比对两个频次表要 O(字符集)；维护 match=已满足种类数，进出窗时 O(1) 增减——覆盖判定变 O(1)。
全正保证"和随窗口扩大单调增、缩小单调减"——合法性单调。有负数（LC 862）要用前缀和 + 单调栈：找 pre[j]−pre[i] ≥ k 的最小 j−i。
窗口 = 同向双指针 + 窗口统计。对撞指针（两数之和）也是双指针但反向。窗口的特殊性在"维护窗口内聚合信息"，而不只是两个下标。
把"替换 k 次"翻译成"窗口内非最高频字符数 ≤ k"——维护 maxFreq 即可判定。求最长窗口 + 容忍度 ≤k 是万能转换句式（1004 同款）。
合法性不单调（负数和）→ 前缀和+哈希（560）/单调栈（862）；求窗口最值 → 单调队列（239）；求所有方案 → 回溯。先验证单调性再写窗口。
Related & References
参考来源（本 deck 结论可溯源至下列一手材料）
| LeetCode 3/76/209/239/424/438 官方题解 | 三类窗口模板与"合法性单调"前提的讨论 |
| CLRS ch（滑动窗口作为 amortized 例）· 挑战程序设计竞赛（虫取法） | 日文系教材的"虫取法"即滑动窗口 |
| oi-wiki.org/basic/two-pointer | 双指针与滑动窗口的中文系统讲解 |
| LeetCode 862 官方题解 | 负数场景的前缀和+单调栈（窗口失效案例） |