所有代码详见：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。通用模板如下：

int left = 0, right = 0;
// window 是窗口内维护的数据结构（hash map / counter / 单调队列等）
while (right < n) {
    // 1. 扩展窗口：加入 right 指向的元素
    window.add(nums[right]);
    right++;

    // 2. 窗口不合法时，收缩左侧
    while (/* 窗口不合法 */) {
        window.remove(nums[left]);
        left++;
    }

    // 3. 此时窗口合法，更新答案
    res = max(res, right - left);
}

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

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

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

③ right 走过的位置还需要回头考虑吗？ 不需要。right 到达位置 i 时，left 之前的所有位置与 i 的组合，要么合法时已记录过答案，要么被判定不合法而跳过——全部处理完毕。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 里面记录，不能在外面。

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

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

具体题目

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

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

解：用 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 每次只引入一个新字符，窗口内最多一个旧副本，位置已知

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 收缩过程中（求最小，沿途记录）

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 收缩之后（求最大，合法时直接记）

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按题目类型总结（二十一）

滑动窗口（深化）