滑动窗口这四个字在Java算法面试里的出现频率比我写过的任何设计模式都高。用Java写题的开发者看到“连续子数组”“子串”这类描述脑子里就应该立刻蹦出这套打法。既然标题叫“滑动窗口 2”我默认你已经见过基础的双指针滑动写法所以这篇会直接聊更关键的东西窗口收缩的时机怎么判断、Java代码里到底有哪些容易出问题的细节、四道高频题怎么一步步写出来、以及我踩过的调试坑。如果你连滑动窗口是什么都还没摸清从这篇开始也没问题我会把原理部分讲得足够直白。滑动窗口解决的核心问题是在一段线性数据上寻找满足某个约束的连续区间暴力两重循环能出结果但面试和实际数据处理都不会满意窗口打法把它压成一次遍历这就是它最大的价值。1. 滑动窗口为什么值得单开一篇先搞懂它快在哪1.1 窗口的本质是“带状态的连续区间”滑动窗口说白了就是左指针和右指针圈出一个连续区间右指针负责扩张、左指针负责收缩区间在遍历过程中像条毛毛虫一样往前爬。但真正让它高效的不是“双指针”这个外壳而是“状态持续维护”这个内核。很多人写暴力解法为什么会慢因为每次枚举一个新的起点都要重新计算一遍这个起点到终点的所有信息。比如求“无重复字符的最长子串”暴力写法里每移动一个起点就要重新扫描到末尾看看哪里开始重复重复扫描的次数多了复杂度自然变成O(n²)。而滑动窗口的做法是手里始终维护一个窗口的完整记录右指针往前走一步我往记录里加一个新字符左指针往前走一步我从记录里删掉一个旧字符。每次只做常数级的增量更新而不是全量重算。我用一个生活化类比来解释你站在一条传送带前检查连续产品的合格区间暴力做法是每移动一个位置就把前面所有产品重新数一遍滑动窗口的做法是手里永远只维护一箱产品的台账传送带往前送一个你从台账里加一个新品、去掉一个旧品随时知道当前箱子里什么情况。整个流水线走完你也只是每个产品进出一次台账工作量线性增长。1.2 时间复杂度的数学直觉滑动窗口的时间复杂度是O(n)这个结论很多面试的人都会背但被追问“为什么内层还有一个while循环复杂度不是O(n²)吗”就卡住了。其实道理很简单right指针从0走到n-1每一步都可能触发left指针的收缩但left指针总共也只能从0走到n-1。也就是说整个算法过程中left指针移动的总次数不会超过nright指针移动的总次数也不会超过n加在一起最多2n次操作。内层那个while无论执行多少次它消耗的都是left指针的总移动额度而不是每次外层循环都重新移动n次所以均摊下来依然是O(n)。这个分析方式是面试加分项。很多人只会写代码讲不清楚复杂度怎么来的而面试官恰恰喜欢在这个点深挖。你如果把“每个元素最多被right加入一次、被left移出一次”这句话说出来在面试官眼里就和背模板的选手拉开了差距。1.3 识别滑动窗口题型的三个信号刷题多了你会发现滑动窗口不是万能的但它有非常明显的适用特征。我总结成三个信号同时看到三个基本就可以往窗口上想。第一个信号题目要求的是连续子数组或子串而不是子序列。子序列允许跳着选窗口是管不了的窗口只能处理原始顺序中连成一体的区间。第二个信号题目里出现了“最长”“最短”“包含”“覆盖”“至少”“不超过”这类对区间整体性质的限定而且这个性质随区间扩大或缩小是单调变化的。什么叫单调窗口越大和越大窗口越大越容易出现重复字符窗口越大越容易覆盖目标字符集。这种单向变化的趋势正是left指针可以放心收缩的依据。第三个信号数据规模提示你需要O(n)解法通常在几万到几十万这个量级O(n²)基本要超时。反过来也要会排除。如果题目要求的是“子序列的某种最优值”窗口直接失效如果要求窗口内元素满足非单调的组合条件比如“窗口内元素互质”之类left收缩的判断依据不成立滑动窗口也无能为力。我见过不少人拿到题就套窗口模板最后套不进去还怀疑自己写错了其实是题型判断就偏了。题目特征是否适合滑动窗口连续子数组/子串求最大最小值适合子序列允许跳选不适合窗口扩大时约束单向变化适合约束不具备单调性不适合数据量在10^5左右适合窗口O(n)通过2. Java实现滑动窗口的3个关键细节指针节奏、统计结构与状态设计2.1 左右指针的移动节奏先加右还是先缩左Java写窗口题骨架就一句话外层while控制右指针扩张内层while控制左指针收缩。但很多人折在“更新答案的位置”上。这里没有一劳永逸的公式关键在于想清楚你手里的窗口在哪个时刻是“候选答案”。拿“无重复字符的最长子串”举例右指针把一个新字符加进来之后窗口可能已经出现重复必须先收缩到合法此时的窗口长度right - left才是有效的候选值所以在收缩之后更新答案。而“长度最小的子数组”这类题右指针加数之后窗口和变大满足条件后开始收缩收缩过程的每一步都可能出现更短的合法窗口所以答案要在收缩过程中持续更新。再比如“最小覆盖子串”收缩到刚好不满足条件的前一步那个窗口才是当前右边界下的最优解。我把这三类情况拆开讲透就是下面这个小节的内容。但先记住一个朴素原则往窗口里加元素时只加右指针指向的元素从窗口移除元素时只移左指针指向的元素。顺序永远是“先改状态再移动指针”这两步的顺序一旦写反窗口状态和指针位置就对不上调试时特别难发现。2.2 频次统计用HashMap还是int数组性能与坑的取舍窗口题最常见的状态就是“某个字符/数字出现了几次”。Java里两条路HashMapCharacter, Integer或者int[128]/int[256]数组。我的习惯很明确只要输入是ASCII字符范围一律用int数组只有值域不可控的大整数场景才用HashMap。int数组的好处不只是快。它避免了Integer装箱拆箱的开销也躲开了一个经典坑HashMap的get方法在键不存在时返回null而null参与加减运算直接抛NullPointerException。用getOrDefault可以规避但每次写起来都得多打几个字符。还有一个更隐蔽的坑Integer有缓存区间-128到127之间的Integer对象用比较可能“碰巧”相等超出这个范围就出错。如果你用map的value做频次判断等值比较一定不要用。用int数组下标就是字符本身值就是int完全没有这些心智负担。提示字符统计用int[128]覆盖ASCII、int[256]覆盖扩展ASCII如果是小写字母题int[26]更省记得减a。如果是数字题且值域可控比如题目告诉你数组元素不超过某个最大值直接开对应长度的数组如果值域很大又稀疏HashMap是合理选择但建议对value做intValue()处理避免自动拆箱带来的潜在问题。2.3 窗口状态设计把“数量”和“种类”分开维护窗口题翻车大多不是指针移动错而是窗口内“状态”没设计对。最典型的是最小覆盖子串这类题既要统计每个字符在窗口里出现了几次又要判断当前窗口是否覆盖了目标串的所有字符。这里有两个概念必须分开目标串某个字符需要多少个以及一共有多少种字符还没被满足。举例目标串是“AAB”那么字符A需要2个、字符B需要1个但“还有几种字符没满足”这个值是2因为A和B都是缺的。如果你用一个计数器统计总缺失个数A缺2个、B缺1个加起来是3这个值在窗口加入一个A后会变成2看起来好像“满足程度”提升了但实际A这种字符依然缺1个缺失种类数还是2。所以正确做法是用一个need数组记录每个字符还缺多少用一个missing变量记录“还有多少种字符没补齐”。need数组的增减在每次加字符、移字符时同步更新但missing只在某个字符的need从正数变为0补齐或从0变为正数重新变缺时才变化。这个设计不是死记硬背的模板而是从问题语义里自然推导出来的。你写窗口题时可以先问自己一句我需要在窗口里追踪哪些独立维度是频次、是和、是乘积还是“哪些条件满足了”把维度列清楚代码结构自然就清晰了。3. 四道高频滑动窗口题实战拆解从无重复子串到固定窗口3.1 无重复字符的最长子串把可变窗口玩明白题目要求给定字符串s找出其中不含重复字符的最长子串长度。这题是可变窗口的入门题也是我建议所有人都能徒手写出来的题。public int lengthOfLongestSubstring(String s) { int n s.length(); int[] freq new int[128]; int left 0, right 0; int ans 0; while (right n) { char c s.charAt(right); freq[c]; right; while (freq[c] 1) { char d s.charAt(left); freq[d]--; left; } ans Math.max(ans, right - left); } return ans; }这段代码最巧妙的地方在于判断是否需要收缩时只检查刚加入的字符c的频次。为什么可以只检查它因为在加入c之前窗口已经是合法窗口没有任何重复字符加入c之后唯一可能让窗口变违法的就是c自己出现了第二次。所以只要freq[c] 1说明c重复了此时收缩左边界把左指针指向的字符一个一个移出去直到c的频次回到1窗口再次合法。这个“破坏条件的一定是新元素”的局部性思维是很多窗口题的快速判断依据。答案在收缩后更新因为right - left此时对应的正是一个合法且可能最长的窗口。空串的情况天然被覆盖因为外层while不会进入ans保持0。3.2 最小覆盖子串窗口里的计数与缺失标记题目给两个字符串s和t在s中找到包含t所有字符含重复字符的最短连续子串没有则返回空串。这题比上一题难一个档次也是面试里区分“会写模板”和“真懂窗口”的经典题。public String minWindow(String s, String t) { int[] need new int[128]; for (char c : t.toCharArray()) need[c]; int missing 0; for (int v : need) { if (v 0) missing; } int left 0, right 0; int minLen Integer.MAX_VALUE; int start 0; int n s.length(); while (right n) { char c s.charAt(right); need[c]--; if (need[c] 0) missing--; right; while (missing 0) { if (right - left minLen) { minLen right - left; start left; } char d s.charAt(left); if (need[d] 0) missing; need[d]; left; } } return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); }这里need数组的含义是“这个字符还缺多少个”初始值是t的需求量。右指针加入字符c时need[c]减一如果need[c]恰好从1变成0说明这个字符种类的缺口被补齐missing减一。注意如果need[c]减成负数说明窗口里这个字符已经盈余了missing不要动因为该字符的种类已经满足了。收缩时的判断是对称的。左指针移出字符d之前先看need[d]是否为0如果为0说明d刚好够用移除它之后缺一个所以missing加一然后need[d]加一。判断时机必须在need[d]变化之前写完再看一眼顺序就明白了。收缩过程中每移动一次left就更新一次答案因为每一次移动都可能让窗口变成“新的合法且更短”的状态。3.3 长度最小的子数组简单题反而最容易错答案位置题目给一个正整数数组nums和一个正整数target找出满足和大于等于target的长度最小的连续子数组并返回长度。这题看着简单但我在实际辅导里发现错误率不低原因就是答案更新位置。public int minSubArrayLen(int target, int[] nums) { int left 0, sum 0; int ans Integer.MAX_VALUE; for (int right 0; right nums.length; right) { sum nums[right]; while (sum target) { ans Math.min(ans, right - left 1); sum - nums[left]; left; } } return ans Integer.MAX_VALUE ? 0 : ans; }答案更新写在while循环开头先记录当前合法窗口长度再收缩。如果把更新写在收缩完成之后记录的很可能是已经不满足条件的窗口长度答案就会偏大。为什么这题要在收缩过程中更新而“无重复字符的最长子串”要在收缩后更新因为前者收缩的每一步都可能得到更短合法窗口后者收缩只是为了排除重复排除完成后窗口才是合法的。这道题还有一个隐藏前提数组必须是正整数。因为正整数保证了sum随窗口扩大单调递增left收缩的时机才有据可依。如果数组里有负数sum不再单调窗口收缩的判断就失效了这题得用前缀和加其他方案。3.4 字符串排列匹配固定窗口的滑动技巧题目给两个字符串s1和s2判断s2是否包含s1的某个排列。翻译成人话就是s2中是否存在一个长度等于s1的连续子串它的字符频次和s1完全一样。这题是固定窗口的典型。窗口长度固定为s1的长度每次移动相当于右边进来一个新字符、左边出去一个旧字符然后比较当前窗口的频次是否与s1一致。直接比较两个HashMap也能过但每次都要全量比较一遍时间常数大。更好的方案是维护差分计数和一个diff变量记录两个频次数组有多少个位置的差异移动窗口时只局部更新diff。public boolean checkInclusion(String s1, String s2) { int n s1.length(), m s2.length(); if (n m) return false; int[] cnt new int[26]; for (int i 0; i n; i) { cnt[s1.charAt(i) - a]; cnt[s2.charAt(i) - a]--; } int diff 0; for (int v : cnt) { if (v ! 0) diff; } if (diff 0) return true; for (int i n; i m; i) { int add s2.charAt(i) - a; int rem s2.charAt(i - n) - a; if (cnt[add] 0) diff; cnt[add]--; if (cnt[add] 0) diff--; if (cnt[rem] 0) diff; cnt[rem]; if (cnt[rem] 0) diff--; if (diff 0) return true; } return false; }diff的维护逻辑是某位置从0变成非0说明多了一处差异diff加一从非0变成0说明差异消失diff减一。每次更新一个字符时先记录旧值是否为0再做频次修改再检查新值是否为0。顺序错了diff就会统计错误。这个局部更新思路不仅适用于这题遇到任何“判断两个窗口内容是否相等”的场景都可以套用。3.5 一个可以直接套用的Java通用模板综合上面几道题我沉淀出一个固定骨架。写新题时你只需要替换“状态更新”和“收缩判断”两处。int left 0, right 0; // 状态频次数组、计数变量、sum等 while (right n) { // 1. 加入右边元素更新状态 // 2. 当窗口违反约束时收缩左边界 while (需要收缩) { // 可选在此处更新答案适合“求最短/最小”类 // 移除左边元素更新状态 left; } // 3. 窗口已经合法更新答案适合“求最长/最大”类 right; }记住两条经验求最短/最小答案常在收缩过程中更新求最长/最大答案常在收缩完成后更新。但这不是铁律关键还是要回到题目语义里确认你用来更新答案的窗口在当时是否满足问题条件。4. 滑动窗口常见Bug排查与调试心得现场实录4.1 死循环left和right的推进顺序写反了我见过最多的bug就是内层while收缩时忘了在循环体最后让left自增导致同一个字符被反复移除程序卡死。另一个常见问题是right的自增写在状态更新之前指针已经移动了窗口状态却没跟上后续判断全部错乱。我的排查习惯是先检查“先改状态再移动指针”这个顺序。右指针扩张时一定是先根据当前right指向的元素更新状态再right左指针收缩时一定是先根据当前left指向的元素更新状态再left。如果反过来了窗口的边界和内容就对不上轻则结果错误重则死循环。4.2 Integer缓存与自动拆箱HashMap统计频次的隐形坑用HashMapCharacter, Integer做窗口统计时有一个藏得很深的坑Integer对象有缓存区间比较在-128到127之间可能返回true超出范围返回false。如果你在窗口题里用比较两个频次是否相等小范围测试数据能过换大范围数据就莫名其妙出错。频次比较一律用intValue()或者直接操作int。另一个是空指针。window.get(c)在键不存在时返回null直接做加减运算会抛NullPointerException。正确写法是getOrDefault(c, 0)。我见过太多初学Java的人在这里栽跟头而且报错信息在力扣上往往被截断不好定位。用int[128]之后这类问题直接消失这也是我强烈建议字符统计用数组的原因。4.3 日志调试法把窗口内容打印出来看遇到窗口题逻辑不对我从来不一上来就断点debug。先打日志打印每次迭代前后的left、right和窗口内容。对于字符串题可以直接打印s.substring(left, right)一眼就能看到当前窗口到底是什么。调试代码长这样左指针、右指针、频次数组、窗口文本四个信息打在一行。跑一遍小数据比如“abcabcbb”观察每行输出的窗口文本变化很快就能看出左指针是否在正确时机收缩、窗口是否在正确范围滑动。调试完记得把打印语句删掉或者用日志开关控制不然提交的时候输出一堆调试信息结果页面上全是日志我自己就犯过这毛病。4.4 验证复杂度的实操方法写完窗口代码我会用三种数据自测。第一题目给的示例验证基本逻辑第二构造最坏情况比如全是相同字符的超长字符串确保left指针持续收缩但不卡死第三构造百万级随机数据体感一下运行时间是否接近线性。如果想更严谨可以在代码里加一个计数器统计内层while的总执行次数。跑完后如果发现总次数约等于n说明每个元素平均被移出一次复杂度没问题如果总次数远超n说明收缩逻辑有重复消耗肯定有bug。注意不要只在示例数据上验证就提交。窗口题最容易栽在空输入、全同字符、目标串长度大于主串这类边界上提前构造好测试用例能省大量提交时间。4.5 为什么有的题先更新答案、有的题后更新一次讲清楚我辅导过不少人对“答案更新位置”始终模糊。这里给一个对比矩阵你对照着看就清楚了。题目类型更新时机原因无重复字符的最长子串收缩完成后更新窗口收缩后才恢复合法此时长度才是候选答案长度最小的子数组收缩过程中更新收缩的每一步都可能产生更短的合法窗口最小覆盖子串收缩过程中更新收缩到不满足条件的前一步窗口刚好合法且最短字符串排列匹配固定窗口每次移动后判断窗口长度固定移动后立即判断即可说到底答案更新位置不是背出来的而是由“哪个时刻的窗口满足题目要求”决定的。你每次写窗口题先问自己这个问题答案位置自然就对了。4.6 我的几个实操习惯最后分享几个我写窗口题一直用的习惯。第一动手写代码前先在一张草稿纸上画出窗口移动的瞬间状态标出left和right的位置以及窗口内容的变化。尤其是可变窗口纸面上能看出左指针什么时候动、右指针什么时候停比直接敲代码清晰得多。第二每写完一段状态更新立刻用一句话描述它的语义比如“这句的意思是把字符c加入窗口频次加一”。如果描述不出来说明状态设计有问题。第三把经典题反复手写直到不依赖模板也能在几分钟内在纸上写出核心逻辑。手写和看代码完全是两回事尤其是指针移动和状态更新的耦合关系只有亲手写几遍才能真正建立肌肉记忆。我个人在实际操作中体会到滑动窗口这套打法之所以在Java算法题里高频出现不只是因为它能帮忙应付面试更因为它是一种通用的区间优化思维任何需要在连续数据上维护动态范围信息的场景都可以先想想“能不能用窗口把全量重算变成增量更新”。这个思路迁移到日志分析、流数据处理、实时统计这类工程问题里照样能派上用场。窗口不大但把它吃透收益远比会背几道题大得多。