所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

一、两类滑动窗口

固定窗口

窗口大小 k 固定，套路是：先构建第一个窗口（i 从 0 到 k-1），然后每次右移一格：加入 nums[i]、移除 nums[i-k]，花费 O(N) 时间。

代码模板（以”最大和”为例）：

int n = nums.size();
int sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];  // 构建第一个窗口
int res = sum;
for (int i = k; i < n; i++) {
    sum += nums[i] - nums[i - k];             // 滑入右、滑出左
    res = max(res, sum);
}

可变窗口

窗口大小不固定，由题目条件决定何时扩张 right、何时收缩 left。通用模板如下（2026-10-24 统一为 for + 闭区间，下面每道题都用这一种）：

int left = 0, res = 0;
for (int right = 0; right < n; right++) {   // ① 右进：right 是 for 循环，从不判断
    window.add(nums[right]);

    while (/* 窗口不合法 */) {                // ② 左缩：只有 while 动 left，一合法就停
        window.remove(nums[left]);
        left++;
    }

    res = Math.max(res, right - left + 1);   // ③ 记录：窗口是闭区间 [left, right]
}

口诀：右进、左缩、记录。

旧版模板写的是 while (right < n) + 先 right++ + 长度 right - left（左开右闭不一致的半开区间），而下面各题的代码又是 for + right - left + 1。两套写法混在笔记里，就是 2026-10-24 默写 1004 时写出 right++ 之后还用 right - left + 1、外层四次都写成 while 的根源。一个模式只留一种写法。

动笔前先写下这一行（2026-10-24 用户两次跳过它，两次都写乱了）：

合法 = ＿＿＿；刚才变的只有＿＿＿；所以 while (＿＿＿)。

例：1004 是「合法 = zeros ≤ k；刚才变的只有 zeros；所以 while (zeros > k)」。3 是「合法 = 所有 cnt ≤ 1；刚才变的只有 cnt[s[right]]；所以 while (cnt[s[right]] > 1)」。每一步都是照上一步抄，不需要灵感。

两条常见误区：

「right 不行就跳过它」——不行。窗口必须连续，跳过一个元素窗口就断了。不合法时永远让它进来，再从左边吐。
「left 动得越多越好」——反了，越少越好。多缩一格窗口就短一格；while 一合法就停，正是为了不多缩。

为什么成立——三个核心问题：

① 为什么用 while 不用 if？ left 每次收缩不预设次数，移到窗口合法为止。用 if 只移一次，可能留着不合法的窗口继续走，得出错误答案。

② left 是主动移还是被迫移？ 被迫的。left 右移的唯一触发条件是窗口不合法。窗口合法时 left 不能动——动了只会让窗口更小，错过更大的答案。while 里每一步都是”不得不走”，没有多余的移动。

③ right 走过的位置还需要回头考虑吗？ 不需要。right 到达位置 i 时，left 之前的所有位置与 i 的组合，要么合法时已记录过答案，要么被判定不合法而跳过——全部处理完毕。right 向前走不会遗漏任何有效组合。

不变量（求最长时）——两条，缺一不可：

每轮缩完，窗口合法；
而且 left 是让它合法的最小位置，即窗口是以 right 结尾的最长合法窗口。

只有第 1 条不够：空窗口永远合法，缩成空的也满足第 1 条，但 res 恒为 0。第 2 条由「while 一合法就停」保证。答案窗口必然以某个位置结尾，right 走到那里时当前窗口不比它短，所以 res 一定记到它。

为什么 left 不回头（一行证明）：[l, r] 不合法 ⇒ [l, r+1] 也不合法（多一个元素只会更差）。所以「以 r 结尾的最小合法左端」L(r) 随 r 单调不减，left 跨过去的位置以后永远用不上。

把所有窗口画成表看（nums = [1,0,0,1,0], k=1，格子 (l, r)，✓ 合法）：

          r=0  r=1  r=2  r=3  r=4
   l=0     ✓    ✓    ✗    ✗    ✗
   l=1          ✓    ✗    ✗    ✗
   l=2               ✓    ✓    ✗
   l=3                    ✓    ✓
   l=4                         ✓

指针只会「往右走一格（right 进）」或「往下走一格（left 出）」，路线是一条只往右下的阶梯，总共不超过 2n 步。

	固定 right（标准版）	固定 left
看表的方式	一列一列，找每列最上面的 ✓	一行一行，找每行最右边的 ✓
外层（每轮 1 格）	right	left
内层（挪到不变量成立）	left 缩到合法	right 扩到扩不动
遇到 ✗	踩进去，再往下走回 ✓	先看一眼，不进去，往下走
空窗口	不用管：每个元素先进后出，计数的账永远平；最坏缩成空窗口，空窗口合法，自然停下	会踩空（走到对角线下方 l > r），此时出窗口的元素根本没进过，不能还额度，必须特判

（「固定 left 会踩空，固定 right 踩错了也不用处理」是用户 2026-10-24 自己总结的。）所以统一写固定 right 的版本。

为什么是 O(N)——摊还分析： 单次 while 可能跑多步（扫过中间的”无效元素”才找到触发收缩的那个），但 left 全程只增不减，整个算法里 left 最多移动 N 次，right 最多移动 N 次，总计 O(2N)。

根本前提——单调性： 滑动窗口能成立，依赖窗口合法性对窗口大小有单调性：

扩大窗口（right 右移）→ 合法性只变差或不变
缩小窗口（left 右移）→ 合法性只变好或不变

两条同时成立，left 和 right 才能都不回头。遇到新题，第一步就是验证这道题是否满足单调性，满足才能用滑动窗口，否则不能用（例如数组含负数时”和 ≥ target”就不满足）。

二、求最大窗口 vs 求最小窗口

left 的触发时机，由”求最大”还是”求最小”决定，两者正好相反：

	求最大窗口（如 1004）	求最小窗口（如 LC 76）
left 移动时机	窗口不合法时	窗口合法时
left 停止条件	停到刚好合法	停到刚好不合法
left 的目标	找第一个合法位置	找最后一个合法位置（沿途记录答案）
记录答案时机	while 收缩之后（合法时直接记）	while 收缩过程中（每步记录，取最小）

这是最容易写错的地方：求最小时，答案要在 while 里面记录，不能在外面。

一句话：最长是缩到合法以后记一次；最短是合法期间每缩一步都记一次，而且要在 left 出窗口之前记。

三、难点：如何定义”合法”

题目类型	合法条件	窗口内数据结构
无重复字符最长子串	所有字符频率 ≤ 1	hash map（字符→频率）
至多 k 种字符	distinct 字符数 ≤ k	hash map
最小覆盖子串	覆盖所有目标字符	hash map + counter
最多替换 k 次后最长连续字符	窗口长度 - 最高频字符数 ≤ k	频率数组
和 ≥ target 最短子数组	sum ≥ target	变量（仅限正数数组）

具体题目

3. Longest Substring Without Repeating Characters（无重复字符最长子串）

题意：找字符串中不含重复字符的最长子串长度。

解法一（推荐，面试先写这个）：计数版，就是通用模板。

合法 = 窗口里每个字符最多 1 次；刚才变的只有 cnt[s[right]]；所以 while (cnt[s[right]] > 1)。

int[] cnt = new int[128];
int left = 0, res = 0;
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    cnt[c]++;
    while (cnt[c] > 1) {                 // 只有刚进来的 c 可能重复
        cnt[s.charAt(left)]--;
        left++;
    }
    res = Math.max(res, right - left + 1);
}

面试时最关键的一句：「刚进来的只有 s[right]，所以只有它可能违规」——上一轮结束时窗口合法，这一轮只多了一个字符。这句话解释了 while 为什么只查一个字符。

解法二（选讲）：跳跃版。 用 last_seen 记录每个字符最后出现的下标。right 走到字符 c 时，若 last_seen[c] >= left（c 在窗口内），直接跳 left = last_seen[c] + 1。

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> last_seen;
    int left = 0, res = 0;
    for (int right = 0; right < s.size(); right++) {
        char c = s[right];
        if (last_seen.count(c) && last_seen[c] >= left) {
            left = last_seen[c] + 1;  // 一跳到位
        }
        last_seen[c] = right;
        res = max(res, right - left + 1);
    }
    return res;
}

蓝图：

维护：last_seen（字符 → 最后出现下标）
不合法：last_seen[c] >= left（说明 c 在窗口内已有一个副本）
收缩：不需要 while，一跳到位 — left = last_seen[c] + 1
为什么能一跳：right 每次只引入一个新字符，窗口内最多一个旧副本，位置已知
被跳过的字符不用吐：它们的 last_seen 停在 left 左边，成了过期值。>= left 这个判断（数组写法里等价于 left = max(left, last[c] + 1)）在用到时把过期值过滤掉——这是懒删除，和 743 Dijkstra 的 if (d > dist[u]) continue; 同一个手法
反例 "abba"：right=3 时 a 的 last 是 0，但 left 已在 2。不过滤的话 left 跳回 1，窗口 "bba" 有重复

两种写法对比：计数版是通用模板（1004／76／424 同一个骨架），状态出窗口时会自己减掉；跳跃版只适用于「最多 1 个」，要自己处理过期位置。2026-10-24 用户第一次默写时把两者混了（用「存位置」的数组做「一格一格缩」的动作，还按位置下标去清字符表），结果一团糟。先选定状态，再写代码。

76. Minimum Window Substring（最小覆盖子串）

题意：字符串 s 和 t，找 s 中包含 t 所有字符（含重复）的最短子串。

解：用 hash map need 记录 t 中每个字符的需求量，变量 missing 表示窗口还缺多少个字符（初始等于 t.size()）。

扩展右侧时，如果加入的字符满足 need[c] > 0（即 t 还需要它），那么 missing--。每次 missing == 0，窗口合法，进入内层循环：先记录本次窗口，再收缩左侧；如果移除的字符使得 need[c] > 0（即窗口刚变得不够了），那么 missing++，退出内层循环。（旧文写成「退出内层循环后记录」，与下面代码不符：那时窗口已经不合法了。）

这里 need 对不在 t 中的字符值会为负，不影响逻辑（负数说明窗口里有富余，移除后仍可能合法）。

string minWindow(string s, string t) {
    unordered_map<char, int> need;
    for (char c : t) need[c]++;
    int missing = t.size();
    int left = 0, start = 0, minLen = INT_MAX;
    for (int right = 0; right < s.size(); right++) {
        if (need[s[right]]-- > 0) missing--;
        while (missing == 0) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
            if (++need[s[left++]] > 0) missing++;
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

时间复杂度 O(

)。

蓝图：

维护：need map（字符 → 还差多少个）+ missing（总共还差多少）
合法：missing == 0
right 进：need[c]--，若结果 >= 0 则 missing--（只有真正需要的字符才减 missing）
left 出：need[c]++，若结果 > 0 则 missing++（从”刚好够”变成”开始缺”才加 missing）
记录答案：在 while 收缩过程中（求最小，沿途记录）

另一种写法：维护”凑齐的字符种类数”

上面那份压缩得很紧，但它的正确性依赖”need[c] 可以为负”这个不显然的性质。另一种常见写法改成维护 formed——已经凑齐的字符种类数，目标是 required（t 中不同字符的种类数）。

string minWindow(string s, string t) {
    unordered_map<char,int> need, window;
    for (char c : t) need[c]++;
    int required = need.size();      // 种类数，不是长度
    int formed = 0;
    int left = 0, start = 0, minLen = INT_MAX;

    for (int right = 0; right < s.size(); right++) {
        char c = s[right];
        window[c]++;
        if (need.count(c) && window[c] == need[c]) formed++;    // 这一种刚好凑齐

        while (formed == required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
            char d = s[left++];
            window[d]--;
            if (need.count(d) && window[d] < need[d]) formed--; // 这一种刚好跌破
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

核心区别是计量口径：数”个”还是数”种”。t = "AABC" 时，missing 初始为 4（按重复计的字符个数），而 required 是 3（A、B、C 三种）。两者都把”窗口合法吗”压成了一次 O(1) 的整数比较。

	`missing` 版	`formed` 版
计数单位	个（含重复）	种
表的数量	1 张（`need` 存差值）	2 张（`need` 固定需求 + `window` 实际计数）
`need[c]` 语义	需求 − 已有，可以为负	纯需求量，从不改变
触发时机	跨越 0 这条线	`window[c]` 与 `need[c]` 相等／跌破
无关字符	不用判断，自动往负走不触发	必须 `need.count(c)` 挡一下
代码量	短（核心两行）	长一倍
复杂度	O(\|s\| + \|t\|)	同左，多一张表，常数略大

两边各自的坑：

missing 版的 if (need[s[right]]-- > 0) missing--;，后置递减和比较挤在一行，改成前置、或把 > 写成 >=，就全错了。

formed 版的保护：

window[c] == need[c] 不能写成 >=。否则 t = "AABC" 时第三个 A 进窗口（window = 3 > need = 2）会再次 formed++，直接算重。只有”恰好凑齐”那一刻才计数。
出窗口的判断要看准是减之前还是减之后：减之后写 window[d] < need[d]，减之前写 window[d] == need[d]。2026-10-24 用户写成「减之后 == need」，结果：多余的 A 出窗口时误减 formed，真正缺 A 时反而不减；而且无关字符（need = 0）从 1 减到 0 时 0 == 0 成立，也误减了。
need.count(c)：订正，其实可以省（用户 2026-10-24 自己发现）。进窗口时 window[c] ≥ 1，无关字符的 need = 0，== 不会成立；出窗口时减完 window[d] ≥ 0，< 0 也不会成立。两个比较对无关字符天然不触发，保留只是为了读起来清楚。旧文写的「不能省，否则无关字符会干扰判断」不对。

missing 版也不需要这道保护，因为它把需求和实际存进了同一个数：无关字符从 0 一路往负走，永远 ≤ 0，两个判断天然都不触发。这也是《总结（十二）》那份旧笔记里写的那句”遇到非 T 串的字符时候，无论加减，出现次数都不可能大于 0”——当年看出了现象，但没说透原因是 need 存的是差值而不是余量。

怎么选：面试写 formed 版，理解上掌握 missing 版。

formed 版每一步都能边写边说人话（”这一种凑齐了／这一种跌破了”），自己不容易写错，讲解也顺。missing 版更短更漂亮，但正确性依赖”need 可以为负”这个隐性性质，值得想通，不一定值得默写。

另外 formed 这种”数种类”的计数器，和 340（至多 K 种不同字符）、992（恰好 K 种）那类以种类数定义合法性的题是同一种语感，迁移更顺。

用户 2026-10-24 默写时的另外两个坑（Java 版）：

记录答案用 < 不是 >（求最短），minLen 必须同时更新（只更新了 start，minLen 永远是 0，永远返回 ""）。
初值用 s.length() + 1 当哨兵（任何合法窗口都不会比 s 长），最后还等于它就返回 ""。

变量名：用 need / have / required / formed / start / minLen。charDistinctRunning 这种名字读一遍要翻译一遍，写长了自己也会乱。

提交前四个用例：t 有重复（"aa"）；找不到（s="a", t="aa" → ""）；整串就是答案（"a","a"）；无关字符出窗口不应动 formed。

438. Find All Anagrams in a String（所有字母异位词）

题意：s 中找出所有 p 的字母异位词的起始下标。

解：与 76 题思路相同，区别在于：窗口大小固定为 p.size()（固定窗口），当 missing == 0 且窗口长度恰好等于 p.size() 时，记录结果。

vector<int> findAnagrams(string s, string p) {
    unordered_map<char, int> need;
    for (char c : p) need[c]++;
    int missing = p.size(), left = 0;
    vector<int> res;
    for (int right = 0; right < s.size(); right++) {
        if (need[s[right]]-- > 0) missing--;
        if (right - left + 1 == p.size()) {
            if (missing == 0) res.push_back(left);
            if (++need[s[left++]] > 0) missing++;
        }
    }
    return res;
}

424. Longest Repeating Character Replacement

题意：字符串只含大写字母，允许替换至多 k 个字符，求替换后最长的连续相同字母子串长度。

解：维护窗口内各字母频率，maxFreq 为窗口内最高频字母的数量。

窗口不合法的条件：(right - left) - maxFreq > k（需要替换的字符数超过 k）。

关键观察：maxFreq 只需要维护历史最大值，不需要在收缩时更新（因为让 maxFreq 减小的窗口不可能是答案）。

int characterReplacement(string s, int k) {
    int freq[26] = {}, maxFreq = 0, left = 0, res = 0;
    for (int right = 0; right < s.size(); right++) {
        maxFreq = max(maxFreq, ++freq[s[right] - 'A']);
        while ((right - left + 1) - maxFreq > k) {
            freq[s[left++] - 'A']--;
        }
        res = max(res, right - left + 1);
    }
    return res;
}

1004. Max Consecutive Ones III

题意：01 数组，最多翻转 k 个 0 为 1，求最长连续 1 的长度。

解：等价于”窗口内 0 的数量 ≤ k”的最长子数组。维护窗口内 0 的计数即可。

int longestOnes(vector<int>& nums, int k) {
    int left = 0, zeros = 0, res = 0;
    for (int right = 0; right < nums.size(); right++) {
        if (nums[right] == 0) zeros++;
        while (zeros > k) {
            if (nums[left++] == 0) zeros--;
        }
        res = max(res, right - left + 1);
    }
    return res;
}

注意此题和第二篇中的 487 题（k=1）是同一类型，1004 是泛化版本。

蓝图：

维护：zeros（窗口内 0 的个数）
不合法：zeros > k
收缩：while（right 只引入 1 个 0，但消除它要扫过中间若干个 1，位置未知）
记录答案：while 收缩之后（求最大，合法时直接记）

面试讲法（30 秒）：right 每次一格进窗口，是 0 就 zeros++；zeros > k 时 left 一直右移、移出 0 就 zeros--，直到合法；此时窗口是以 right 结尾的最长合法窗口，更新答案。left 不回头：窗口变大只会 0 更多。每个元素进出各一次，O(n) 时间 O(1) 空间。——面试官最想听的是「不变量」和「为什么 left 不回头」这两句。

三题一个骨架：

题	允许翻几个 0	写法
485	0	一个计数器就够（遇 1 加一，遇 0 清零）；面试写这个，不要拿窗口套 Easy
487	1	模板 k=1；数据流版只记 `lastZero` 一个变量，O(1)
1004	k	模板；数据流版用队列存 0 的位置，O(k)

follow-up：数据流（不能回头读 nums[left]）

k=1（487）：只记最后一个 0 的位置。新 0 进来时先 left = lastZero + 1，再 lastZero = right。顺序反了就把新 0 也踢掉，退化成 485。lastZero 初值 -1 是哨兵：第一个 0 进来时 left = 0，不用特判。
任意 k：队列存窗口里 0 的位置，队头是最早进来的 0。新 0 进来时 先 offer，再 if (size() > k) left = poll() + 1。顺序反了（先判断满没满再 poll），k = 0 时会对空队列 poll 出 null。这个写法也不需要 -1 哨兵：left 只在真的踢掉一个 0 时才更新，没踢之前停在初值 0——487 里 -1 + 1 算出来的那个 0，在这里就是 left 的初值。

Deque<Integer> zeros = new ArrayDeque<>();
int left = 0, res = 0;
for (int right = 0; right < nums.length; right++) {
    if (nums[right] == 0) {
        zeros.offer(right);                  // 先进
        if (zeros.size() > k) left = zeros.poll() + 1;   // 再判断
    }
    res = Math.max(res, right - left + 1);
}

2026-10-24 默写的反面教材：第一版写成「right 贪心扩到底 + left 一次缩一格」双 while，没定开闭区间（right++ 后用 right-left+1），最后用 return res - usedK 把样例凑对了。样例对不上，回去查不变量，绝不在 return 上加减。

239. Sliding Window Maximum（滑动窗口最大值）

题意：固定窗口大小为 k，求每个窗口的最大值。

解：暴力 O(NK)，优化到 O(N) 需要单调递减队列（deque 存下标）。

队列保持单调递减：加入新元素前，把队尾所有比新元素小的下标弹出（它们永远不可能是后续窗口的最大值了）。同时，若队头下标不在当前窗口内（即 deq.front() < i - k + 1），弹出队头。每个下标最多入队和出队一次，总时间 O(N)。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> deq;  // 存下标，单调递减（对应值）
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        while (!deq.empty() && nums[deq.back()] < nums[i])
            deq.pop_back();
        deq.push_back(i);
        if (deq.front() < i - k + 1) deq.pop_front();
        if (i >= k - 1) res.push_back(nums[deq.front()]);
    }
    return res;
}

此题是单调队列的经典应用，与单调栈是兄弟结构：

单调栈解决”下一个更大/更小元素”（全局角度）
单调队列解决”固定窗口内的最大/最小值”（局部角度）

904. Fruit Into Baskets

题意：整数数组代表水果种类，两个篮子各装一种，求能连续摘的最多水果数。

解：等价于”窗口内最多 2 种不同数字”的最长子数组，即 340 题的 k=2 特例。用 hash map 统计窗口内每种水果的数量，当种类超过 2 时收缩左侧。

int totalFruit(vector<int>& fruits) {
    unordered_map<int, int> cnt;
    int left = 0, res = 0;
    for (int right = 0; right < fruits.size(); right++) {
        cnt[fruits[right]]++;
        while (cnt.size() > 2) {
            if (--cnt[fruits[left]] == 0) cnt.erase(fruits[left]);
            left++;
        }
        res = max(res, right - left + 1);
    }
    return res;
}

992. Subarrays with K Different Integers

题意：整数数组，求恰好包含 k 种不同数字的子数组数量。

解：直接维护”恰好 k 种”比较难，因为收缩左侧时无法保证合法。

技巧：恰好 k 种 = 至多 k 种 - 至多 (k-1) 种。

“至多 k 种”的可变窗口计数方法：当窗口合法时，以当前 right 结尾的合法子数组数量就是窗口大小 right - left + 1（left 可以在 [left, right] 任意位置开始都合法）。

int atMostK(vector<int>& A, int k) {
    unordered_map<int, int> cnt;
    int left = 0, res = 0;
    for (int right = 0; right < A.size(); right++) {
        if (cnt[A[right]]++ == 0) k--;
        while (k < 0) {
            if (--cnt[A[left]] == 0) k++;
            left++;
        }
        res += right - left + 1;
    }
    return res;
}

int subarraysWithKDistinct(vector<int>& A, int k) {
    return atMostK(A, k) - atMostK(A, k - 1);
}

总结

滑动窗口的本质是：用 left/right 两个指针在 O(N) 时间内遍历所有”有意义”的子数组，通过维护窗口状态来避免重复计算。

四个核心问题：

窗口内维护什么：频率 map、计数器、单调队列……
何时收缩 left：求最大时在不合法时动；求最小时在合法时动（两者相反）
何时记录答案：求最大 → while 外记录；求最小 → while 内记录
while 还是一跳：right 引入的违规位置已知且恰好一个 → 一跳到位；否则 → while

进阶方向：单调队列是滑动窗口的重要补充，用于 O(1) 查询窗口内最大/最小值（239 题），在动态规划优化中也有应用（见后续总结）。

Leetcode按题目类型总结（二十一）

滑动窗口（深化）