【Java实习面试算法冲刺】滑动窗口

第3类题型：滑动窗口

为什么滑动窗口题你明明刷过，一到面试还是容易收缩错

很多同学第一次见滑动窗口，会觉得它只是“双指针换个名字”。因为代码结构经常也是left、right两个变量，再套一层while，表面上不难。但真正到了面试现场，滑动窗口反而很容易暴露出三类问题：

• 你会背模板，却说不清窗口里到底维护了什么状态。
• 你知道要收缩，却解释不出为什么此时收缩不会漏答案。
• 你能把代码写个大概，但固定窗口和可变窗口经常混着用。

如果你现在正处在“Easy 还能做，Medium 一追问就乱”的阶段，滑动窗口很值得单独拿出来练。读完这篇，你至少要把 3 件事练熟：先判断题目是不是连续区间问题、先定义窗口状态再写模板、能在面试里解释清楚窗口什么时候扩张、什么时候收缩、什么时候更新答案。

1. 核心知识点

滑动窗口常见在字符串和数组题里，核心是维护一个连续区间[left, right]，让这个区间始终满足某个条件，或者在扩张和收缩过程中寻找最优答案。

你可以把它理解成双指针的一个特化版本，但它更强调“窗口内部状态”的维护，比如：

• 当前窗口中每个字符出现了几次。
• 当前窗口和是多少。
• 当前窗口是否满足“无重复”“包含所有目标字符”等条件。

最常见的框架是：

intleft=0;for(intright=0;right<s.length();right++){// 把 s[right] 纳入窗口while(窗口需要收缩){// 移出 s[left]left++;}// 更新答案}

难点不在模板，而在两个问题：

• 什么时候扩张。
• 什么时候收缩。

动画辅助理解：先扩张，再在窗口失效时收缩

滑动窗口最适合用3. 无重复字符的最长子串建立第一印象。你可以先打开本地动画页：

滑动窗口：无重复字符分步动画

这个动画最值得观察的是 4 步：

• right先把新字符纳入窗口。
• 一旦发现窗口冲突，比如某个字符重复，先别重开，而是移动left修复状态。
• 只有窗口重新合法后，才更新答案。
• 每个元素最多进窗口一次、出窗口一次，所以总复杂度才能压到O(n)。

拿s = "abca"举例，窗口状态变化是这样的：

2. 这类题在面试里考什么

滑动窗口题主要考两个能力：

• 你能不能把“连续区间”抽象成状态维护问题。
• 你能不能清楚地定义窗口何时有效、何时无效。

面试官往往会追问：

• 你的窗口里存的是什么状态。
• 为什么这个条件满足时要收缩。
• 更新答案是在收缩前还是收缩后。

如果这三个问题答不清楚，代码大概率也写不稳。

3. 高频题清单

4. 这类题最容易犯的 3 个错误

1. 只记住了双层while结构，却没定义窗口状态。
2. 不知道什么时候该收缩，导致答案更新时机全乱。
3. 字符串题里频次数组和HashMap切换不清，写得又慢又乱。

5. 代表题精讲 1

题目

209. 长度最小的子数组

思路

题目要求找到和大于等于target的最短连续子数组长度。因为数组元素都是正数，所以窗口和随着右边扩张只会变大，这就给了我们收缩窗口的依据。

做法：

1. 右指针不断向右扩张，把新元素加入窗口和。
2. 当窗口和>= target时，说明当前窗口已经满足要求，可以尝试收缩左边，看看能否变得更短。
3. 每次收缩前更新最短长度。

Java 代码

classSolution{publicintminSubArrayLen(inttarget,int[]nums){intleft=0;intsum=0;intbest=Integer.MAX_VALUE;for(intright=0;right<nums.length;right++){sum+=nums[right];while(sum>=target){best=Math.min(best,right-left+1);sum-=nums[left];left++;}}returnbest==Integer.MAX_VALUE?0:best;}}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

边界提醒

这题能直接用可变长度滑动窗口，一个很关键的前提是：数组元素都是正数。因为全是正数时，窗口右扩后，窗口和只会变大；一旦sum >= target，左边收缩才有明确意义。

如果数组里允许负数，这个单调性就没了。此时你不能直接套这个模板，往往要改用前缀和、单调队列或别的思路。这一点在面试里如果你能主动说出来，专业度会明显更高。

如果这是面试现场，你可以这样说

这题我会用滑动窗口，因为题目找的是连续子数组，而且数组元素都是正数，所以窗口和随右指针扩张单调增加。当窗口和达到目标时，就可以移动左指针尝试收缩，从而找到更短的满足条件的区间。每个元素最多进窗口一次、出窗口一次，所以整体复杂度是O(n)。

6. 代表题精讲 2

题目

438. 找到字符串中所有字母异位词

思路

这题的关键是：窗口长度固定为p.length()，只要窗口里的字符频次和p完全一致，这个窗口就是一个异位词。

因为字符只包含小写字母，所以可以直接用长度为 26 的数组做计数，而不是HashMap。

一种常用做法是维护一个差分数组：

• 先把p的字符频次加进去。
• 扫描窗口时，把进入窗口的字符减掉。
• 当窗口长度超过p.length()时，把离开窗口的字符再加回来。
• 每次窗口长度刚好等于p.length()时，检查计数数组是否全为 0。

Java 代码

importjava.util.ArrayList;importjava.util.List;classSolution{publicList<Integer>findAnagrams(Strings,Stringp){List<Integer>result=newArrayList<>();if(s.length()<p.length()){returnresult;}int[]count=newint[26];for(charc:p.toCharArray()){count[c-'a']++;}intleft=0;for(intright=0;right<s.length();right++){count[s.charAt(right)-'a']--;if(right-left+1>p.length()){count[s.charAt(left)-'a']++;left++;}if(right-left+1==p.length()&&allZero(count)){result.add(left);}}returnresult;}privatebooleanallZero(int[]count){for(intvalue:count){if(value!=0){returnfalse;}}returntrue;}}

复杂度

• 时间复杂度：O(26 * n)，也可以视为O(n)
• 空间复杂度：O(1)

边界提醒

这里用int[26]的前提是题目明确说了字符串只包含小写字母。如果字符集扩大到大小写字母、Unicode 或任意字符流，就要根据题目条件改成HashMap<Character, Integer>或更大的计数结构，而不是死背26。

如果这是面试现场，你可以这样说

这题我会把它看成固定长度窗口。窗口长度始终等于p.length()，只要窗口中的字符频次和p一样，就说明这个窗口是一个异位词。因为只涉及 26 个小写字母，所以我会优先用计数数组维护频次，而不是HashMap。这样写法更直接，常数也更小。

7. 其余题模板与关键片段

3. 无重复字符的最长子串

核心是窗口中不能出现重复字符：

int[]count=newint[128];intleft=0;intbest=0;for(intright=0;right<s.length();right++){count[s.charAt(right)]++;while(count[s.charAt(right)]>1){count[s.charAt(left)]--;left++;}best=Math.max(best,right-left+1);}

567. 字符串的排列

和异位词问题本质接近，只是问是否存在，因此你可以把它当成“找到一个满足条件的固定长度窗口就立刻返回true”：

classSolution{publicbooleancheckInclusion(Strings1,Strings2){if(s1.length()>s2.length()){returnfalse;}int[]count=newint[26];for(charc:s1.toCharArray()){count[c-'a']++;}intleft=0;for(intright=0;right<s2.length();right++){count[s2.charAt(right)-'a']--;if(right-left+1>s1.length()){count[s2.charAt(left)-'a']++;left++;}if(right-left+1==s1.length()&&allZero(count)){returntrue;}}returnfalse;}privatebooleanallZero(int[]count){for(intvalue:count){if(value!=0){returnfalse;}}returntrue;}}

这类固定窗口题有一个很实用的面试表达：窗口长度由题目直接给定，所以你的关注点不是“何时收缩到合法”，而是“每次窗口长度超过目标值时，把最左边那个元素移出去，让窗口长度重新回到固定值”。

8. 什么时候用固定长度窗口，什么时候用可变长度窗口

你可以用一个很快的判断法：

• 题目要求“长度恰好为k的子串 / 子数组”，优先想固定长度窗口。
• 题目要求“满足某条件的最长 / 最短连续区间”，优先想可变长度窗口。

常见对应关系是：

真正写代码前，你最好先用一句话把窗口状态说出来：

• 我维护的是窗口内字符频次。
• 我维护的是窗口和。
• 我维护的是当前窗口是否还合法。

9. 错题本记录方式

滑动窗口题建议记录：

• 我维护的窗口状态是什么。
• 窗口何时有效、何时无效。
• 我为什么要在这个时机收缩。
• 这题是可变长度窗口还是固定长度窗口。

10. 面试前 3 分钟速记

• 连续子串 / 子数组，优先想滑动窗口。
• 先定义窗口里维护什么状态，再写模板。
• 正数数组的最短 / 最长区间题，常见可变长度窗口。
• 异位词、排列问题，常见固定长度窗口。
• 小写字母优先用int[26]，别一上来就上HashMap。

11. 最后总结：滑动窗口不是背模板，而是先定义状态

如果你只能记住一句话，那就是：滑动窗口题真正的核心不是while模板，而是“窗口里维护什么状态，窗口在什么条件下算合法”。

面试时你只要能按这个顺序去讲，思路就不容易乱：

1. 先判断这是不是连续区间问题。
2. 再判断这是固定长度窗口还是可变长度窗口。
3. 明确窗口里维护的是频次、和，还是合法性条件。
4. 最后再决定答案是在扩张后更新，还是在收缩到合法后更新。

这样你不只是会写一道题，而是真的开始掌握滑动窗口这一类题的共性。

上一篇：【Java实习面试算法冲刺】双指针
下一篇：正在路上……

感谢阅读，记得点赞、关注、收藏，欢迎各位评论区交流！！！