所有代码详见：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);
}

关键点：

right 只增不减，left 只增不减，两者合计最多移动 2N 次 → O(N)。
窗口内维护什么数据结构，取决于题目对”合法”的定义。
更新答案的时机可能在”恰好合法时”（求最长），也可能在”刚变不合法前”（求最短）。

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

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

具体题目

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(

)。

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 是泛化版本。

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：窗口不合法时
何时记录答案：合法时（求最长）or 刚变不合法前（求最短）

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

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

滑动窗口（深化）