滑动窗口

本章题海战术

典型例题	leetcode题目	leetcode链接
子数组最大平均数 I	leetcode 643	https://leetcode.cn/problems/maximum-average-subarray-i/description/
字符串的排列	leetcode 567	https://leetcode.cn/problems/permutation-in-string/description/
找到字符串中所有字母异位词	leetcode 438	https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
滑动窗口最大值	leetcode 239	https://leetcode.cn/problems/sliding-window-maximum/description/
无重复字符的最长子串	leetcode 3	https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
长度最小的子数组	leetcode 209	https://leetcode.cn/problems/minimum-size-subarray-sum/description/
替换后的最长重复字符	leetcode 424	https://leetcode.cn/problems/longest-repeating-character-replacement/description/
最小覆盖子串	leetcode 76	https://leetcode.cn/problems/minimum-window-substring/description/
最大连续1的个数 III	leetcode 1004	https://leetcode.cn/problems/max-consecutive-ones-iii/description/
水果成篮	leetcode 904	https://leetcode.cn/problems/fruit-into-baskets/description/

滑动窗口

🎤 面试现场口语化作答

面试官提问：

说一下你对滑动窗口算法的理解，它适合解决什么问题？

候选人回答：

面试官您好，滑动窗口本质是双指针技巧的一个分支，专门解决数组、字符串里的「连续子序列最优解」问题。

它的核心思路是用左右两个指针维护一个 “窗口”，通过指针移动让窗口在序列上滑动，利用增量更新避免重复计算，把暴力法的 O (n²) 时间复杂度优化到 O (n)。

能用滑动窗口的前提是窗口状态具有单调性—— 右指针右移时，窗口的状态只会朝一个方向变化（比如窗口和只会变大、重复字符数只会变多），所以左指针不需要回退，每个元素最多进出窗口各一次，保证线性复杂度。

主要分两类场景：

1. 固定大小窗口：窗口长度固定，比如求长度为 k 的子数组最大和；
2. 可变大小窗口：窗口长度不固定，求满足条件的最长 / 最短子串，比如最长无重复子串、最小覆盖子串。

💡 核心分类与原理图解

1 固定大小窗口

窗口长度提前确定，每次整体向右滑动一位，仅做增量更新。

2 可变大小窗口

窗口长度不固定，右指针扩展窗口，不满足条件时左指针收缩窗口，动态维护合法窗口。

⌨️ Java 核心代码模板（带技术亮点）

1 固定窗口模板（长度为 k 的子数组最大和）

public int maxSubArraySum(int[] nums, int k) {
    int n = nums.length;
    int windowSum = 0;
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }
    int maxSum = windowSum;

    // 窗口滑动
    for (int right = k; right < n; right++) {
        // 增量更新：减去移出的左端元素，加上新入的右端元素
        windowSum = windowSum - nums[right - k] + nums[right];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

技术亮点：

• 时间复杂度严格 O (n)，仅一次遍历，避免暴力法重复计算窗口和
• 空间复杂度 O (1)，仅使用常数级额外变量
• 增量更新思想，窗口滑动时仅做 2 次运算，无冗余计算

2 可变窗口模板（无重复字符的最长子串）

public int lengthOfLongestSubstring(String s) {
    // 技术亮点：用数组替代HashMap，ASCII字符集大小128，访问O(1)且无哈希碰撞
    int[] count = new int[128];
    int left = 0;
    int maxLen = 0;
    char[] chars = s.toCharArray();

    for (int right = 0; right < chars.length; right++) {
        char c = chars[right];
        count[c]++;
        // 窗口不满足条件（出现重复）时，循环收缩左边界
        while (count[c] > 1) {
            count[chars[left]]--;
            left++;
        }
        // 窗口合法，更新最大长度
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

技术亮点：

• 数组替代哈希表，字符计数性能提升明显，面试高频加分项
• while 循环收缩左边界，确保每次右指针移动后窗口都处于合法状态
• 提前转为字符数组，避免 charAt 频繁做边界检查（细节优化）
• 左右指针均不回退，每个元素仅进出窗口一次，严格线性复杂度

⚠️ 技术难点与解决方案对照表

技术难点	对应解决方案
窗口边界越界、左右指针交叉	右指针遍历上限为数组长度 - 1；左指针始终≤右指针，收缩时加边界校验
可变窗口收缩时机搞反	求「最长合法窗口」：不满足条件时收缩；求「最短合法窗口」：满足条件时收缩
元素计数不准确、出窗漏减	严格遵循「入窗 + 1，出窗 - 1」配对原则；收缩左指针时必须同步更新计数
误用滑动窗口（不满足单调性）	仅窗口状态单调变化时可用；正负值混合的子数组和问题改用前缀和 + 哈希表
多条件窗口判断逻辑混乱	将窗口合法性封装为独立方法，分层校验条件，避免多层嵌套 if
滑动窗口求极值（如最大值）	普通窗口无法 O (n) 解决，搭配单调队列维护窗口内极值

🔥 LeetCode 高频面试考题清单

固定窗口类（入门必刷）

题号	题目名称	难度	核心考点
643	子数组最大平均数 I	简单	固定窗口基础模板
567	字符串的排列	中等	固定窗口 + 字符计数匹配
438	找到字符串中所有字母异位词	中等	固定窗口 + 异位词判断
239	滑动窗口最大值	困难	固定窗口 + 单调队列（大厂高频难题）

可变窗口类（核心高频）

题号	题目名称	难度	核心考点
3	无重复字符的最长子串	中等	可变窗口入门模板
209	长度最小的子数组	中等	求最短合法窗口模板
424	替换后的最长重复字符	中等	窗口内最多字符数统计
76	最小覆盖子串	困难	多条件覆盖匹配（面试常客）

真实面试模拟

真实面试模拟

面试官 😊：

同学你好，今天咱们来聊聊算法题里的“滑动窗口”。不用紧张，就当你我是在讨论技术方案。先来个基础的：你能一句话说清楚滑动窗口的本质是什么吗？

候选人 💡：

好的面试官。滑动窗口本质上就是两个同向移动的指针，配合一个可动态维护的状态。我们把数组或字符串想象成一排房间，窗口就是左右指针夹住的区间。右指针负责扩展窗口去“探索”，左指针在状态不满足时收缩窗口来“补锅”，整个过程就像毛毛虫一样一拱一拱地往前走，同时不断用当前合法的窗口更新答案。

面试官 🤔：

不错，很形象。那你能不能现场写一个通用的模板出来？用你最熟悉的 Java 就行，要能直接套用的那种。

候选人 ⌨️：

没问题，我写一个左闭右开 [left, right) 的版本，这个边界处理方式能避免很多坑：

public int slidingWindowTemplate(String s) {
    // 状态容器：可按需换成 int[128] 或 HashMap
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int ans = 0;
    while (right < s.length()) {
        // 1️⃣ 右指针扩张，加入新元素并更新状态
        char c = s.charAt(right);
        right++;
        window.put(c, window.getOrDefault(c, 0) + 1);

        // 2️⃣ 判断窗口何时需要收缩（条件按题目定）
        while (window.get(c) > 1) { // 例：出现重复字符
            char d = s.charAt(left);
            left++;
            window.put(d, window.get(d) - 1);
        }

        // 3️⃣ 窗口严格合法后，更新最优解
        ans = Math.max(ans, right - left);
    }
    return ans;
}

面试官 👀：

这个模板里你把 right++ 写在最前面，为什么？另外内层用 while 而不是 if，能解释下吗？

候选人 🎯：

这两个点刚好是保证算法鲁棒性的关键。

• 先 right++ 并更新状态，能严格保证窗口区间是 [left, right)，此时窗口长度直接用 right - left 计算，完全不用纠结 +1 还是 -1，代码心智负担极低。
• 内层用 while 是因为有些场景下收缩一次可能不够。比如字符串 "abccba"，当右指针扫到第二个 c 时窗口内有重复，左指针仅仅右移一位可能还在重复区间里，必须连续收缩直到没有重复字符为止。所以用 while 才能保证收缩后窗口一定是合法的。

面试官 👍：

细节抠得很细。那如果让你把这个流程画成图给新人看，你会怎么画？

候选人 ✍️：

我会用下面的流程状态图，一眼就能看清循环的骨架和决策点：

面试官 🧐：

基本功挺扎实。接下来咱们聊聊这个算法的技术难点，你平时用滑动窗口踩过哪些坑？又是怎么解决的？

候选人 📋：

滑动窗口的难点几乎都集中在状态维护和边界条件上。我整理过一个清单，面试和实际编码中特别管用：

难点	典型场景	我的解决方案
何时收缩窗口？	最长无重复子串：重复字符出现时就要收缩	用 while(窗口内有重复) 精准驱动，保证缩到合法才更新答案
收缩时状态如何更新？	计数类窗口：字符频次、和、乘积等	先更新状态移除 left 元素，再执行 left++，顺序反了会导致统计错位
如何保证 O(n)？	看似双层循环容易被质疑是 O(n²)	左右指针各自最多移动 n 次，内层 while 总执行次数 ≤ n，整体严格 O(n)
区间开闭处理	right 越界、长度计算易错	统一使用左闭右开 [left, right)，长度直接 right - left，杜绝 ±1 错误
容器选择	字符串只有 ASCII 字符时用 HashMap 太重	字符集明确时直接用 int[128]，读写速度、内存都有优势
多条件窗口	最小覆盖子串这类需要满足多个字符频次要求	额外维护一个 matchCount，当某个字符频次达标时 +1，滑出时若从达标变不达标则 -1，避免每次全量检查 window

面试官 📈：

这总结放到公司 wiki 里都能当标准文档了。那你能不能快速列举一下滑动窗口在 LeetCode 上的高频考题？最好能一句话点名核心考点。

候选人 🚀：

常见的“必刷题”大概就这些，我按考察方向分了个类：

题号	题目	核心考点	难度	一句话口诀
3	无重复字符的最长子串	快慢指针 + Set/数组	🟡	窗口内不能有重复，重复即收缩
209	长度最小的子数组	正数数组 + 目标和	🟡	累加和 ≥ target 就收缩，记录最小长度
76	最小覆盖子串	变长窗口 + 多条件匹配	🔴	双哈希表 + matchCount，先扩找到可行解，再收缩求最优
438	找到字符串中所有字母异位词	固定窗口同步滑动	🟡	窗口长度固定为 p.length()，每次左右同步右移
567	字符串的排列	同上，但返回布尔	🟡	同 438，一旦窗口匹配立即返回 true
424	替换后的最长重复字符	窗口内最多替换 k 个	🟡	窗口长度 - 窗口内最频字符次数 > k 即收缩
1004	最大连续1的个数 III	翻转 k 个 0 的最长子数组	🟡	窗口内 0 的个数 > k 时收缩
904	水果成篮	至多包含两种元素的最长子数组	🟡	元素种类 > 2 时收缩

面试官 🎓：

很全面。最后我想听听你的算法“品味”——你觉得什么情况下必须用滑动窗口？什么时候绝对不能碰？

候选人 🌟：

这是问题的精髓。滑动窗口适用的场景必须满足单调性：

• 随着右指针右移，窗口扩大，条件只会往“更容易被破坏”的方向发展；
• 左指针右移，窗口缩小，条件只会往“更容易满足”的方向发展。

这种单向性保证了我们可以用双指针免回溯地剪枝。如果题目不具备这个单调性（比如数组里有负数，求等于某和的最长子数组），滑动窗口就不适用，得老老实实用前缀和+哈希表。把这一点悟透，我们选算法就不是拍脑袋，而是有理有据的推导。

面试官 😄：

非常好！今天的交流就到这里，你的表现很稳，回去等下一轮通知吧～ （暗中已经把通过的小勾打上了 ✅）