第3类题型滑动窗口为什么滑动窗口题你明明刷过一到面试还是容易收缩错很多同学第一次见滑动窗口会觉得它只是“双指针换个名字”。因为代码结构经常也是left、right两个变量再套一层while表面上不难。但真正到了面试现场滑动窗口反而很容易暴露出三类问题你会背模板却说不清窗口里到底维护了什么状态。你知道要收缩却解释不出为什么此时收缩不会漏答案。你能把代码写个大概但固定窗口和可变窗口经常混着用。如果你现在正处在“Easy 还能做Medium 一追问就乱”的阶段滑动窗口很值得单独拿出来练。读完这篇你至少要把 3 件事练熟先判断题目是不是连续区间问题、先定义窗口状态再写模板、能在面试里解释清楚窗口什么时候扩张、什么时候收缩、什么时候更新答案。文章目录第3类题型滑动窗口1. 核心知识点动画辅助理解先扩张再在窗口失效时收缩2. 这类题在面试里考什么3. 高频题清单4. 这类题最容易犯的 3 个错误5. 代表题精讲 1题目思路Java 代码复杂度边界提醒如果这是面试现场你可以这样说6. 代表题精讲 2题目思路Java 代码复杂度边界提醒如果这是面试现场你可以这样说7. 其余题模板与关键片段[3. 无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/)[567. 字符串的排列](https://leetcode.cn/problems/permutation-in-string/)8. 什么时候用固定长度窗口什么时候用可变长度窗口9. 错题本记录方式10. 面试前 3 分钟速记11. 最后总结滑动窗口不是背模板而是先定义状态1. 核心知识点滑动窗口常见在字符串和数组题里核心是维护一个连续区间[left, right]让这个区间始终满足某个条件或者在扩张和收缩过程中寻找最优答案。你可以把它理解成双指针的一个特化版本但它更强调“窗口内部状态”的维护比如当前窗口中每个字符出现了几次。当前窗口和是多少。当前窗口是否满足“无重复”“包含所有目标字符”等条件。最常见的框架是intleft0;for(intright0;rights.length();right){// 把 s[right] 纳入窗口while(窗口需要收缩){// 移出 s[left]left;}// 更新答案}难点不在模板而在两个问题什么时候扩张。什么时候收缩。动画辅助理解先扩张再在窗口失效时收缩滑动窗口最适合用3. 无重复字符的最长子串建立第一印象。你可以先打开本地动画页滑动窗口无重复字符分步动画这个动画最值得观察的是 4 步right先把新字符纳入窗口。一旦发现窗口冲突比如某个字符重复先别重开而是移动left修复状态。只有窗口重新合法后才更新答案。每个元素最多进窗口一次、出窗口一次所以总复杂度才能压到O(n)。拿s abca举例窗口状态变化是这样的步骤当前窗口发生了什么为什么这样做right 0a放入a当前无冲突答案可更新为1right 1ab放入b当前无冲突答案可更新为2right 2abc放入c当前无冲突答案可更新为3right 3abca放入第二个a后出现重复这时不能直接更新答案而要移动left直到窗口重新合法收缩后bca左边的a被移出窗口恢复无重复但最长答案仍是32. 这类题在面试里考什么滑动窗口题主要考两个能力你能不能把“连续区间”抽象成状态维护问题。你能不能清楚地定义窗口何时有效、何时无效。面试官往往会追问你的窗口里存的是什么状态。为什么这个条件满足时要收缩。更新答案是在收缩前还是收缩后。如果这三个问题答不清楚代码大概率也写不稳。3. 高频题清单题目来源难度高频属性209. 长度最小的子数组面试经典 150Medium基础高频3. 无重复字符的最长子串LeetCode 热题 100Medium真实面经高频438. 找到字符串中所有字母异位词LeetCode 热题 100Medium高频 Medium567. 字符串的排列面试经典 150Medium高频 Medium4. 这类题最容易犯的 3 个错误只记住了双层while结构却没定义窗口状态。不知道什么时候该收缩导致答案更新时机全乱。字符串题里频次数组和HashMap切换不清写得又慢又乱。5. 代表题精讲 1题目209. 长度最小的子数组思路题目要求找到和大于等于target的最短连续子数组长度。因为数组元素都是正数所以窗口和随着右边扩张只会变大这就给了我们收缩窗口的依据。做法右指针不断向右扩张把新元素加入窗口和。当窗口和 target时说明当前窗口已经满足要求可以尝试收缩左边看看能否变得更短。每次收缩前更新最短长度。Java 代码classSolution{publicintminSubArrayLen(inttarget,int[]nums){intleft0;intsum0;intbestInteger.MAX_VALUE;for(intright0;rightnums.length;right){sumnums[right];while(sumtarget){bestMath.min(best,right-left1);sum-nums[left];left;}}returnbestInteger.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{publicListIntegerfindAnagrams(Strings,Stringp){ListIntegerresultnewArrayList();if(s.length()p.length()){returnresult;}int[]countnewint[26];for(charc:p.toCharArray()){count[c-a];}intleft0;for(intright0;rights.length();right){count[s.charAt(right)-a]--;if(right-left1p.length()){count[s.charAt(left)-a];left;}if(right-left1p.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 或任意字符流就要根据题目条件改成HashMapCharacter, Integer或更大的计数结构而不是死背26。如果这是面试现场你可以这样说这题我会把它看成固定长度窗口。窗口长度始终等于p.length()只要窗口中的字符频次和p一样就说明这个窗口是一个异位词。因为只涉及 26 个小写字母所以我会优先用计数数组维护频次而不是HashMap。这样写法更直接常数也更小。7. 其余题模板与关键片段3. 无重复字符的最长子串核心是窗口中不能出现重复字符int[]countnewint[128];intleft0;intbest0;for(intright0;rights.length();right){count[s.charAt(right)];while(count[s.charAt(right)]1){count[s.charAt(left)]--;left;}bestMath.max(best,right-left1);}567. 字符串的排列和异位词问题本质接近只是问是否存在因此你可以把它当成“找到一个满足条件的固定长度窗口就立刻返回true”classSolution{publicbooleancheckInclusion(Strings1,Strings2){if(s1.length()s2.length()){returnfalse;}int[]countnewint[26];for(charc:s1.toCharArray()){count[c-a];}intleft0;for(intright0;rights2.length();right){count[s2.charAt(right)-a]--;if(right-left1s1.length()){count[s2.charAt(left)-a];left;}if(right-left1s1.length()allZero(count)){returntrue;}}returnfalse;}privatebooleanallZero(int[]count){for(intvalue:count){if(value!0){returnfalse;}}returntrue;}}这类固定窗口题有一个很实用的面试表达窗口长度由题目直接给定所以你的关注点不是“何时收缩到合法”而是“每次窗口长度超过目标值时把最左边那个元素移出去让窗口长度重新回到固定值”。8. 什么时候用固定长度窗口什么时候用可变长度窗口你可以用一个很快的判断法题目要求“长度恰好为k的子串 / 子数组”优先想固定长度窗口。题目要求“满足某条件的最长 / 最短连续区间”优先想可变长度窗口。常见对应关系是题型信号更适合的窗口模型典型题长度固定、比较频次、判断是否存在固定长度窗口438、567求最短满足条件区间可变长度窗口209求最长合法区间可变长度窗口3真正写代码前你最好先用一句话把窗口状态说出来我维护的是窗口内字符频次。我维护的是窗口和。我维护的是当前窗口是否还合法。9. 错题本记录方式滑动窗口题建议记录我维护的窗口状态是什么。窗口何时有效、何时无效。我为什么要在这个时机收缩。这题是可变长度窗口还是固定长度窗口。10. 面试前 3 分钟速记连续子串 / 子数组优先想滑动窗口。先定义窗口里维护什么状态再写模板。正数数组的最短 / 最长区间题常见可变长度窗口。异位词、排列问题常见固定长度窗口。小写字母优先用int[26]别一上来就上HashMap。11. 最后总结滑动窗口不是背模板而是先定义状态如果你只能记住一句话那就是滑动窗口题真正的核心不是while模板而是“窗口里维护什么状态窗口在什么条件下算合法”。面试时你只要能按这个顺序去讲思路就不容易乱先判断这是不是连续区间问题。再判断这是固定长度窗口还是可变长度窗口。明确窗口里维护的是频次、和还是合法性条件。最后再决定答案是在扩张后更新还是在收缩到合法后更新。这样你不只是会写一道题而是真的开始掌握滑动窗口这一类题的共性。上一篇【Java实习面试算法冲刺】双指针下一篇正在路上……感谢阅读记得点赞、关注、收藏欢迎各位评论区交流