年初在准备面试的时候我把LeetCode Top100按标签重新刷了一遍。刷到“滑动窗口”这个分类时一个很直观的感受是数组和字符串类的题只要题干里出现“连续子数组”“子串”“最长/最短”这几个词八成都能用滑动窗口把O(n²)级别的暴力解法优化到O(n)。Top100里的滑动窗口题目不算多但几乎每道都是面试高频题尤其对Java后端候选人来说手写一个干净的滑动窗口比背一堆八股文更能让面试官认可你的基本功。这篇文章我就围绕Top100里出现频率最高的几道滑动窗口题用Java把通用模板、完整代码、易错点和面试官爱追问的点一次讲清楚。刚开始刷题的同学可以直接照着敲已经刷过一遍的也可以把这里面的细节当作查漏补缺的清单。1. 滑动窗口到底是什么从LeetCode 3看解题边界先说一个最容易让新手绕晕的问题什么样的题才应该想到滑动窗口我自己的判断标准很朴素题目要求在一个数组或字符串里找一个连续区间并且这个区间要满足某个条件比如不重复、和大于等于target、包含全部目标字符最后求的是最长长度、最短长度或者符合条件的区间个数。只要同时满足“连续”和“满足条件”这两个特征滑动窗口就是最优解候选。1.1 暴力解法为什么不可行拿Top100里的经典题LeetCode 3“无重复字符的最长子串”举例。如果不用滑动窗口最直接的暴力思路是枚举所有子串逐个判断子串里有没有重复字符记录最长长度。一个长度为n的字符串子串总数是O(n²)每个子串用HashSet判断是否重复又要O(n)整体复杂度O(n³)。字符串长度稍微到几千就完全跑不动了。面试时我不会直接否定暴力解而是会把它的复杂度算给面试官看然后说“这里存在大量重复计算每次枚举子串时之前已经判断过的窗口内容被反复遍历”。这个过渡非常自然也是面试官想听的优化动机。1.2 窗口的左右指针到底在做什么滑动窗口的核心可以理解成一把可以伸缩的尺子right指针负责向右扩展把新元素纳入窗口left指针负责收缩把不满足条件的元素从窗口左侧移出。整个过程里窗口内的数据始终被维护在一个状态结构里比如HashSet、HashMap或者直接用数组当哈希表。用尺子来类比你想找一根绳子上连续一段没有打结的部分最长有多长。right像你的右手不断往右摸发现这段里有结重复字符了就把left这只左手往右挪直到把那个结排除窗口。左右手都只往一个方向走所以总移动次数是2n复杂度O(n)。这就是滑动窗口能在Top100里横行霸道的原因每个元素最多进窗口一次、出窗口一次。1.3 什么样的题不能硬套滑动窗口滑动窗口能成立的隐含前提是窗口的收缩条件具备单调性。也就是说窗口变大时“不满足条件”的趋势不可逆窗口缩小时才会重新满足条件。LeetCode 3里窗口内出现重复字符后继续右扩只会让重复情况更严重必须收缩LeetCode 209里窗口和超过target后继续右扩只会让和更大所以可以收缩。一旦题目出现负数、需要排序、窗口内求中位数等场景就要小心了后面第5章会专门讲一个反例。2. 一套通用模板先写出来再谈每道题的差异我刷完Top100里所有滑动窗口题之后最大的收获不是背会了某道题而是总结出一套几乎所有“同向双指针收缩型”滑动窗口都能往里套的Java模板。套模板这件事没有任何丢人的面试时能快速写出框架再根据题目改收缩条件和答案更新位置就是高效的应试能力。2.1 模板里五个核心变量int left 0; // 左指针窗口左边界 int right 0; // 右指针窗口右边界开区间 int valid 0; // 窗口内已满足条件的计数根据题意变化 // 窗口状态结构int[] 或 HashMap while (right s.length()) { // 1. 右扩把 right 指向的元素加入窗口 // 2. 更新窗口状态 // 3. right 移动右指针 // 4. 判断是否需要收缩while 循环 while (需要收缩的条件) { // 5. 收缩过程中可能需要更新答案 // 6. 左缩移除 left 指向的元素更新窗口状态 // 7. left 移动左指针 } // 8. 收缩结束后的窗口才合法有时候答案在这里更新 }第一次看这个模板会觉得有点抽象我拆开解释。窗口本身是一个左闭右开区间也就是[left, right)初始时left 0, right 0窗口里什么都没有。每一次循环先把right对应的元素纳入窗口然后检查当前窗口是否违反了约束条件如果违反了就移动left收缩直到约束重新被满足。2.2 模板里最难的答案到底在哪更新这是最多人问我的问题。我的经验是先判断这道题求的是“满足条件的最长”还是“满足条件的最短”。求最短时往往要在收缩循环内部更新答案因为收缩的过程就是在尝试“当前窗口能不能更短一点”求最长时通常要等收缩结束、窗口重新合法后再更新答案因为那时的窗口才是满足条件的最长状态。类型典型题目收缩时机答案更新位置最长无重复子串LeetCode 3窗口内出现重复字符收缩结束后更新maxLen最短子数组LeetCode 209窗口和 target收缩循环内部更新minLen覆盖子串LeetCode 76窗口已覆盖全部目标字符收缩循环内部更新minLen这个区别我一开始也搞反过。LeetCode 3如果我直接在出现重复字符时更新长度那窗口本身就是非法的算出来的长度也偏大LeetCode 209如果我在收缩结束后再更新最短的那个子数组往往已经被收缩过去了答案会漏掉。所以做题前先问自己一句我更新答案时当前的窗口“合法”吗如果合法那可以在循环外更新如果必须收缩后才合法那答案更新位置就要跟着收缩走。2.3 收缩用while还是if怎么判断模板里的第4步有人用if有人用while这是区分初学者和熟练者的地方。判断标准就一条一次收缩是否一定能让窗口重新合法。LeetCode 3里窗口内某个字符出现两次你把left左移一位重复字符不一定被移出去可能要连续移好几位所以必须用while循环直到完全无重复。LeetCode 209里窗口和超过target后减去一次left就能让和变小但可能减完还是大于target同样需要while。基本上只要“满足条件”是一个累积状态就必须用while持续收缩到合法为止。3. 最长子串与最短子数组Top100两道必考题的完整拆解这一章把LeetCode 3和LeetCode 209放在一起讲因为它们正好代表了“最长类”和“最短类”两种最典型的答案更新方式。这两道题是Top100里出现频率最高的滑动窗口入门题也是我面试时最常被要求手写的题没有之一。3.1 LeetCode 3无重复字符的最长子串题目要求给定字符串s找出其中不含重复字符的最长子串长度。核心思路是窗口内维护一个计数数组记录每个字符在当前窗口中出现的次数。public int lengthOfLongestSubstring(String s) { int[] window new int[128]; // 覆盖ASCII字符 int left 0, right 0; int maxLen 0; while (right s.length()) { char c s.charAt(right); right; window[c]; // 窗口内出现重复字符收缩left直到没有重复 while (window[c] 1) { char d s.charAt(left); left; window[d]--; } // 收缩完成后[left, right) 是合法无重复窗口 maxLen Math.max(maxLen, right - left); } return maxLen; }这里有一个很多人容易写错的点判断重复字符时不是检查整个窗口有没有重复而是检查右扩进去的那个字符的出现次数是否大于1。因为在此之前窗口本身就是合法的唯一可能破坏合法性的就是新加进来的c所以while (window[c] 1)就足够了。复杂度上每个字符最多进窗口一次、出窗口一次时间复杂度O(n)空间上用了长度为128的数组是O(1)的。面试时如果能主动说出“字符串的字符范围是ASCII所以我用固定数组替代HashMap申请/装拆箱”会是一个很加分的细节。3.2 我在这道题上踩过的坑这道题看似简单我刷的时候踩过一个很隐蔽的坑一开始我用的是HashSetCharacter来维护窗口合法时add收缩时remove。Set本身没问题问题出现在我每次收缩只移除一个字符却用while判断窗口是否合法导致代码逻辑不清晰最后干脆改用计数数组。数组的好处是你能精确知道某个字符在窗口里出现的次数而Set只能告诉你“在不在”没法回答“有几个”所以在需要处理重复字符计数时数组或Map才是正确的选择。3.3 LeetCode 209长度最小的子数组题目要求给定一个正整数数组nums和一个正整数target找出数组中满足其和大于等于target的长度最小的连续子数组。这道题有个重要的前提数组元素全是正数。正因为全是正数窗口右扩时和一定变大左缩时和一定变小才存在单调性滑动窗口才能用。public int minSubArrayLen(int target, int[] nums) { int left 0, sum 0; int minLen Integer.MAX_VALUE; for (int right 0; right nums.length; right) { sum nums[right]; while (sum target) { minLen Math.min(minLen, right - left 1); sum - nums[left]; left; } } return minLen Integer.MAX_VALUE ? 0 : minLen; }注意这里我把right的更新写在了for循环里其实和之前的模板本质一样。收缩条件是sum target只要满足条件我们就尝试把left往右移每移一次都记录一次当前窗口长度因为移动left后窗口可能仍然满足sum target那它就更短了。这个“在收缩循环内部一直更新答案”的模式就是最短类题目的标准写法。如果不用滑动窗口也可以用前缀和加二分前缀和数组有序对每个起点二分查找终点复杂度O(n log n)。但滑动窗口能做到O(n)面试时可以先给出滑动窗口解再提一句“如果面试官要求进一步考虑负数场景需要换思路因为负数会破坏单调性”。3.4 面试延伸把长度换成数量LeetCode 209有个常见变体比如LeetCode 713“乘积小于K的子数组”求的是乘积小于K的连续子数组个数。这题其实不用维护最小长度而是每次right右扩后收缩到乘积小于K时right - left 1就是“以right为结尾的满足条件的子数组个数”累加即可。它能这么做的原因是固定右端点后左端点落在[left, right]区间内的所有连续子数组都满足条件。面试中遇到“求个数”的题目都可以想想这个套路。4. 异位词与最小覆盖子串从固定窗口到动态收缩如果说第3章的两道题是滑动窗口的“单数组状态”那么Top100里还有一类是“多字符匹配”问题典型代表就是LeetCode 438“找到字符串中所有字母异位词”和LeetCode 76“最小覆盖子串”。这类题的特点是窗口内不只是统计某个条件而是要跟一个目标字符串做匹配。刷透这两道Top100里的字符串滑动窗口基本就扫平了。4.1 LeetCode 438所有字母异位词题目要求给定两个字符串s和p在s中找出所有p的异位词的起始索引。异位词意味着字符种类和数量完全相同只是顺序可以不同。这道题的窗口大小是固定的就是p的长度。我的写法是用两个长度为26的数组分别记录目标字符串p的字符频数和当前窗口的字符频数再用一个valid变量记录“已经匹配上的字符种类数”。public ListInteger findAnagrams(String s, String p) { ListInteger res new ArrayList(); if (s.length() p.length()) return res; int[] need new int[26]; int[] window new int[26]; int needValid 0; for (char c : p.toCharArray()) { if (need[c - a] 0) needValid; need[c - a]; } int left 0, right 0, valid 0; while (right s.length()) { int in s.charAt(right) - a; right; if (need[in] 0) { window[in]; if (window[in] need[in]) valid; } // 固定窗口长度窗口长度等于p长度时开始收缩 while (right - left p.length()) { if (valid needValid) { res.add(left); } int out s.charAt(left) - a; left; if (need[out] 0) { if (window[out] need[out]) valid--; window[out]--; } } } return res; }这个写法里最微妙的地方是valid的维护逻辑只有当window[c]的个数恰好等于need[c]时valid才加一当left移出元素时如果移出前window[c]恰好等于need[c]说明匹配被破坏valid减一。用valid去和needValid比较而不是每次循环都遍历26个位置比对省掉了不必要的计算。4.2 LeetCode 76最小覆盖子串LeetCode 76是Top100滑动窗口里综合难度最高的一道给定字符串s和t在s中找到包含t全部字符包括重复字符的最短子串。所谓覆盖就是要求窗口内每个目标字符的数量都不少于t中的数量。这道题我建议直接用HashMap因为字符范围不固定也更贴近通用解法。public String minWindow(String s, String t) { MapCharacter, Integer need new HashMap(); MapCharacter, Integer window new HashMap(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } int left 0, right 0; int valid 0; int start 0, minLen Integer.MAX_VALUE; while (right s.length()) { char c s.charAt(right); right; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } // 窗口已经覆盖t中所有字符尝试收缩找更短 while (valid need.size()) { if (right - left minLen) { minLen right - left; start left; } char d s.charAt(left); left; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); }需要注意两个细节。第一个window.get(c).equals(need.get(c))必须用equals如果图省事用在字符频数超过127后Integer缓存机制失效两个相同数值的Integer对象比较会返回false导致valid计数错误。这个问题我在真实面试中转写代码时踩过当时和面试官排查了好一会儿。第二个细节收缩条件是valid need.size()也就是窗口里每个目标字符都齐了。valid表示“与need中要求数量匹配的字符种数”当它等于need的key数量时说明全部目标字符都已就位。4.3 把76题的模板套回438题如果把76题看成一类“动态收缩最短窗口”438题就是它的“固定窗口”版本一个求最短一个求所有匹配起点。面试官有时候会连续追问这两题本质上就是想看你知不知道它们底层是同一套东西。能写出76题再解释一句“438题只是把收缩条件从‘覆盖全部t字符’改成‘窗口长度等于p长度’”基本就能过关。另外如果面试官问“窗口内状态用数组还是HashMap”我的回答是字符范围确定且很小比如26个字母用数组遍历快、省内存字符范围不确定或者字符集很大比如Unicode全量用HashMap。这两个选择背后都是空间和通用性的权衡。5. 滑动窗口最大值为什么这题脱离双指针模板Top100里有一道题叫LeetCode 239“滑动窗口最大值”名字里带“滑动窗口”但它和前几章的解法完全不同这也是很多人刷到这道题时楞住的地方。给定数组nums和滑动窗口大小k要求返回每个窗口内的最大值。如果套用第2章的模板思路会变成窗口每次右移一格然后遍历窗口内k个元素找最大值。那样总复杂度是O(nk)在LeetCode上基本会超时。5.1 这种题缺的是什么前面几道题能靠双指针优化核心在于窗口状态可以被“增量维护”——计数增减、字符匹配数增减这些操作都是O(1)的。但“最大值”这个状态很难增量维护你只知道新进来的值是多少却不知道被移出去的值是不是当前最大值如果是第二大的值是谁又不知道。所以需要一个额外的数据结构能同时支持新增一个值、删除一个旧值、获取当前最大值三者都要高效。5.2 单调队列的核心思想这类题的标准解法是维护一个单调递减的双端队列。队列从头到尾的元素值递减队首永远是当前窗口的最大值。具体规则就两条新元素入队前从队尾弹出所有小于等于它的元素。因为只要新元素还在窗口里这些更小的元素永远不可能成为最大值了。left指针移出窗口时检查队首元素的下标是否已经离开窗口如果离开了就弹出队首。队列里存的是元素下标不是值。这一点很关键因为判断元素是否还在窗口内必须用下标而且下标又能反过来拿到值一举两得。public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] res new int[n - k 1]; DequeInteger deque new LinkedList(); int idx 0; for (int i 0; i n; i) { // 队首下标离开窗口范围弹出 while (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } // 从队尾弹出所有小于等于当前值的下标维护单调递减队列 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } deque.offerLast(i); // 窗口从下标k-1开始完整每右移一次队首就是窗口最大值 if (i k - 1) { res[idx] nums[deque.peekFirst()]; } } return res; }每个元素最多入队一次、出队一次所以总复杂度O(n)空间O(k)。如果面试官问为什么用而不是这是因为两个值相等时老下标先离开窗口新下标存活时间更长保留新下标更优所以把等于当前值的旧下标全部弹出。5.3 Java语言层面的实现细节Java里ArrayDeque不支持插入null元素而且它虽然可以作为双端队列但按索引访问不方便所以更推荐用LinkedList来实现。如果你的代码对性能更敏感可以直接用一个数组模拟双端队列用一个head指针和一个tail指针这会比容器类快不少但面试时写LinkedList完全够用重点是思路能讲清楚。还有一点值得和面试官主动聊单调队列只能解决“窗口最值”问题如果把题目改成“滑动窗口中位数”单调队列就不适用了因为中位数要求知道窗口中间位置的数需要用到双堆或者有序数据结构比如TreeMap复杂度也会变成O(n log k)。这种延伸问题在Top100之外的进阶题里很常见面试时能说出这个区别说明你真的理解单调队列的边界。6. 面试刷题实测Top100滑动窗口题优先级与高频追问最后这一章我想聊点刷题方法论。Top100里的滑动窗口题数量不多但每道题的难度梯度很清晰刷题顺序直接决定效率。我自己的建议是先刷第三、四章那四道基础题最后再啃239这种“披着滑动窗口外衣”的单调队列题。6.1 题目优先级参考题目难度核心考点建议优先级LeetCode 3 无重复字符的最长子串中等窗口收缩、答案更新时机必刷LeetCode 209 长度最小的子数组中等最短类收缩、单调性前提必刷LeetCode 438 找到字符串中所有字母异位词中等固定窗口、字符匹配必刷LeetCode 76 最小覆盖子串困难HashMap窗口、valid计数高优先LeetCode 239 滑动窗口最大值困难单调双端队列高优先LeetCode 567 字符串的排列中等438题的变体选刷LeetCode 30 串联所有单词的子串困难438题升级版偏难有余力再刷6.2 面试时的高频追问和应对我整理了几个面试官在滑动窗口题上特别爱追问的问题提前准备好可以省去现场思考的时间。问为什么用while而不是if收缩回答思路窗口状态是累积的一次收缩不一定能让窗口重新满足合法性条件。用LeetCode 3举例窗口里可能有多个重复字符需要持续收缩到完全没有重复为止。if只能用于单次移除必然修复问题的场景而这种场景在滑动窗口题中很少见。问答案为什么放在这里更新这是最致命的一问。回答思路先说明当前窗口是否合法。最长类题目的窗口在收缩后才合法所以在收缩外更新最短类题目的收缩过程本身就是尝试更短结果的过程所以在收缩内更新。要能结合具体题目把这两句话说到位。问如何证明复杂度是O(n)回答思路left和right都只往一个方向移动每个元素最多被right加进来一次、被left移出去一次所以总操作次数不超过2n均摊到每一次循环是O(1)整体O(n)。这个证明简洁又有力。问如果数组里包含负数怎么办对于LeetCode 209这类题目负数的出现会破坏“窗口扩大和一定变大”的单调性滑动窗口就不适用了。一般的替代思路是前缀和配合有序结构/二分来寻找满足条件的区间代价是复杂度上升。这个追问考的是你对算法适用边界的理解。6.3 我刷这七道题踩过的几个真实坑再说几个代码层面容易翻车的地方都是我实际刷题记录里翻过车的。第一个是Java的Integer比较问题。我在写76题的时候window.get(c)和need.get(c)直接用比较在小字符串测试用例时一切正常一提交就报错。原因前面讲过Integer在-128到127之间有缓存超出这个范围后比较的是引用而不是值。这个坑在LeetCode这类在线判题系统里非常隐蔽因为小数据和大数据的表现不一致。第二个是LeetCode 3里用SetCharacter的坑。用Set虽然能判断“有没有重复”但当收缩left时你不知道当前窗口里同一个字符出现了几次没法安全地把它从Set中移除。比如窗口从左到右是a b c a你移出第一个aSet里还剩一个a如果此时直接set.remove(a)窗口状态就错了。必须用计数数组或Map记录每个字符在窗口内的次数。第三个是结果初始化和边界判断。76题如果没有覆盖子串要返回空字符串209题如果整个数组加起来都不够target要返回0239题当k大于数组长度时直接返回空数组。这些边界条件看似简单但面试手写时最容易漏建议每道题收尾前都主动用一两个极简用例过一遍比如字符串为空、k1、kn这几种。6.4 考场上的表达顺序最后分享一个我整理出的“滑动窗口题面试表达顺序”适用于上述所有题目。第一步听清题意后先确认边界条件比如字符串是否可能为空、数组是否全是正数、窗口大小是否固定。第二步给出暴力解法并快速分析复杂度明确说出“这里重复计算了窗口内容”。第三步提出滑动窗口说清楚左指针和右指针各代表什么、窗口状态如何维护、什么时候收缩、答案在哪里更新。第四步手写代码边写边讲解每段逻辑的目的。第五步主动跑一两个例子证明代码正确并说明复杂度。这个过程看起来繁琐但实际练习几次之后会非常流利。面试官不会因为你会做某道题给你加分但会因为你能把思路讲清楚、把边界踩住而给你加分。我自己在刷完Top100这组滑动窗口题之后有个习惯不再把每道题当成独立的题目去背答案而是把它们归纳成模板里的不同参数组合。比如把“窗口状态”从计数换成字符匹配把“收缩条件”从重复出现换成覆盖完成把“答案更新位置”从收缩外放到收缩内所有题目就都串起来了。后面再遇到陌生题目我会先问自己三个问题窗口是什么、什么时候扩、什么时候缩。想清楚这三件事代码基本就稳了。希望你也能用这种方式把这组题吃透面试时碰到类似题目至少心态上会稳很多。