刷过LeetCode的朋友应该都有这种感觉有些题型你第一次做完全没思路看答案觉得妙不可言自己上手写又bug不断。滑动窗口就是这样一类题。作为Java后端开发者无论是准备校招、社招还是跳槽大厂LeetCode Top100里的滑动窗口题目几乎是必刷的——它考察的不仅是对双指针的理解更是对“状态维护”和“边界控制”的掌控力。我见过太多候选人栽在“窗口怎么收缩”“什么时候更新答案”这两个问题上。这篇内容我会把Top100里滑动窗口相关的核心题目全部拆开从最朴素的暴力解法推导到最优解把每一步设计的原因讲透同时给出可以直接背下来的Java模板和一套我在实战中验证过的调试方法。1. 滑动窗口算法的核心思想与通用模板很多人把滑动窗口想复杂了其实它就是在一维数组或字符串上维护一个区间通过左右两个指针的移动来遍历所有可能的“合法区间”。这个思想的本质是用两个指针确定窗口边界用某种数据结构维护窗口内的状态窗口移动时只更新变化的部分而不是每次重新计算整个窗口。1.1 为什么需要滑动窗口从暴力解法的困境说起拿“长度最小的子数组”这道题举例LeetCode 209。题目要求找出和大于等于target的最短连续子数组暴力做法是枚举每个起点和终点计算子数组和时间复杂度O(n²)。当数据规模到10⁵量级O(n²)直接超时。滑动窗口能把这类问题优化到O(n)。为什么能做到核心在于利用了数据的前后关联性当右指针向右移动一个位置时新窗口的和可以通过“旧窗口的和 新加入元素”得到不需要从头加一遍。同样左指针向右移动时只需减掉移出的元素。这样每个元素只会被操作两次——进窗口一次、出窗口一次整体就是O(n)。这个思路看起来平平无奇但它解决了一类普遍的问题模式“连续子数组/子串 满足某种条件的最值”。只要题目同时满足这两个特征滑动窗口就大概率是正解。1.2 双指针实现窗口固定窗口与可变窗口滑动窗口分两种形态固定大小窗口和可变大小窗口。固定窗口大小是“右边每走一步左边也跟着走一步”窗口宽度恒定可变窗口则是右指针不断扩张当窗口内不满足条件时左指针收缩窗口宽度动态变化。前者代表是“字符串的排列”LeetCode 567后者代表是“无重复字符的最长子串”LeetCode 3。搞清楚题目要的是哪一种是解题的第一步也是最容易出错的地方。判断方法很简单如果题目要求“连续子数组/子串”且条件只与子数组本身有关就用可变窗口如果条件里提到了固定长度比如“长度为k的子数组”用固定窗口。更多时候条件是以“窗口内元素满足某个约束”的形式给出的这种情况几乎都是可变窗口。1.3 Java代码实现一套能应对90%题目的窗口框架在Java里实现滑动窗口我建议统一用这套结构public int slidingWindow(int[] nums, int target) { int left 0, right 0; int ans Integer.MAX_VALUE; int sum 0; while (right nums.length) { // 1. 窗口加入right位置的元素 sum nums[right]; right; // 2. 当窗口不满足条件时收缩左侧 while (sum target) { // 3. 更新答案 ans Math.min(ans, right - left); // 4. 窗口移出left位置的元素 sum - nums[left]; left; } } return ans Integer.MAX_VALUE ? 0 : ans; }这套框架的核心逻辑只有四步但越简单的框架越容易在小细节上出错。第一步和第四步是对称的一个负责进入窗口、一个负责移出窗口务必保证操作的变量是正确的。第二步while循环是“收缩”的触发条件必须想清楚“什么时候窗口不合法”。第三步答案更新位置决定你求的是最大值还是最小值是窗口内还是窗口外。我见过很多同学把答案更新放在收缩之前或之后得到的结果差之毫厘、谬以千里——这其实不是一个效率问题而是一个语义问题你要求的答案到底是哪个窗口状态的答案。1.4 复杂度分析与性能边界滑动窗口的时间复杂度是O(n)空间复杂度取决于窗口内维护的数据结构。如果只维护一个整数变量如和、计数空间O(1)如果题干涉及字符/字母需要维护一个频率表空间O(字符集大小)通常是O(128)或O(26)都可以视作O(1)。这个复杂度是面试中的标准答案但很多背模板的人答不出来“为什么每个元素只进一次出一次”。关键在于内层的while循环虽然看起来是嵌套的但实际上left指针在整个过程中最多移动n次所以内外层总操作次数是2n不是n²。注意不是所有“连续子数组”问题都能用滑动窗口前提是窗口收缩时能“无损”地丢弃状态。如果移出某个元素后无法恢复窗口的历史状态滑动窗口就不适用这时可能要考虑前缀和、二分或者其他思路。后面我会专门说这个问题。2. Top100高频滑动窗口题目逐题拆解入门到进阶Top100里滑动窗口类的题目数量不算多但每一道都是经典中的经典。我按照从易到难排序逐题过一遍重点讲清楚“为什么这么设计”和“坑在哪里”。2.1 长度最小的子数组LeetCode 209从暴力到滑动窗口的推导这题是滑动窗口的入门题题干是找一个连续子数组使它的和大于等于target返回最短长度。一开始暴力枚举起点终点O(n²)在leetcode上会超时。优化方向就是避免重复计算——固定左端点右端点向右移动时累加和自然增长一旦和满足条件这个区间就是“以当前左端点为起点”的满足条件的最短区间接下来左端点右移继续找新的满足条件的区间。这里有个细节很多初学者会忽略为什么一旦满足条件就要立即收缩左指针而不是继续扩大右指针因为题目求的是“最短长度”在左端点固定的情况下右端点越靠右长度越长而当前右端点已经是第一个让和大于等于target的位置了再往右只会更长所以这个状态可以直接放弃移动左端点探索以新左端点为起点的可能性。这就是“滑动”二字的含义窗口一边扩大、一边收缩遍历的是所有可能成为最优解的窗口状态而不是所有可能的子数组。Java实现用前面那套模板即可代码不再重复。要注意返回值是0的情况如果整个数组的和都小于target说明不存在符合条件的子数组返回0。很多人在这个边界上栽跟头。2.2 无重复字符的最长子串LeetCode 3经典中的经典这是我在面试中见过频率最高的一道题也是滑动窗口思想最直观的体现。题干是找出字符串中不含重复字符的最长子串。思路是维护一个窗口右指针不断向右扩展同时用一个HashSet或boolean数组记录窗口内出现的字符当新加入的字符已经在窗口中出现过就不断移动左指针直到把这个重复字符移出窗口为止。每次更新答案时取当前窗口长度和历史最大值的较大者。这道题有几个可以优化的小细节。第一判断重复用HashSet还是boolean[128]在Java里如果字符集明确是ASCII直接用boolean[128]会更快省去自动装箱和哈希计算的开销如果是Unicode字符用HashSet更稳妥。第二左指针移动的停止条件不是“窗口里没有重复字符”而是“新加入的那个字符已经被移除”所以要等窗口内不再包含right指向的字符为止。这个边界写错会导致窗口收缩不足或过度收缩。代码示例public int lengthOfLongestSubstring(String s) { boolean[] seen new boolean[128]; int left 0, ans 0; for (int right 0; right s.length(); right) { char c s.charAt(right); while (seen[c]) { seen[s.charAt(left)] false; left; } seen[c] true; ans Math.max(ans, right - left 1); } return ans; }注意这里的while循环是收缩的核心一旦发现新字符已经出现过就一直移动左指针把重复字符“挤”出去等while结束后再放入新字符。如果写成if判断就只会移出一个字符出错的概率极高。我当时第一次写就吃了这个亏后来总结出一个规律当收缩条件是“直到某个条件不再满足”时用while当收缩条件是“每次最多移出一个”时用if。面试时如果能把这一步说清楚面试官会认为你真的理解算法而不是背模板。2.3 找到字符串中所有字母异位词LeetCode 438模板题的教科书这道题要求找出所有是p的字母异位词的子串的起始索引。所谓字母异位词就是两个字符串含有的字母相同、排列不同。题目本质是在s中找所有长度等于len(p)的子串且每个字母的出现次数与p完全相同。这题可以直接用固定窗口大小实现窗口大小始终是len(p)右指针每走一步左指针也跟着走一步窗口内维护一个长度为26的计数数组记录当前窗口内每个字母出现的次数。每移动一步比较窗口内计数和p的计数是否相等如果相等当前左指针位置就是一个答案。Java代码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]; for (char c : p.toCharArray()) { need[c - a]; } int len p.length(); for (int right 0; right s.length(); right) { window[s.charAt(right) - a]; if (right len) { window[s.charAt(right - len) - a]--; } if (Arrays.equals(window, need)) { res.add(right - len 1); } } return res; }这个写法比标准模板更简洁因为它用一个“延迟删除左指针”的方式代替了显式的左指针变量。理解这个写法对于理解“固定窗口”的移动逻辑非常有帮助。另一种常见的写法是维护一个diff变量记录窗口和need有多少个字母的次数不同从而把比较时间从O(26)降到O(1)。面试时如果时间充裕可以提一嘴这个优化。2.4 最小覆盖子串LeetCode 76最考验细节的滑动窗口这题是滑动窗口里的压轴题虽然是困难难度但核心思想并不复杂用need数组统计t中各字符的需求量用window数组统计当前窗口内各字符的拥有量右指针不断向右扩展直到窗口内已经覆盖t的全部字符然后尝试收缩左指针在保持覆盖的条件下使窗口最短。但真正写起来到处都是坑。第一如何判断“已经覆盖”可以维护一个变量matched记录“当前窗口中满足需求的字符种类数”。当某个字符在窗口中的数量达到need中要求数量时matched加1当移出一个字符导致该字符数量低于需求时matched减1。这样判断覆盖就变成了比较matched和need中非零字符种类数是否相等。如果用遍历need数组的方式每次都要O(字符集大小)虽然也能过但效率差不少。第二收缩的条件。这道题里左指针收缩的前提是“移除left指向字符后窗口仍然覆盖t”也就是移除之后不会导致matched减小。一旦发现移除会导致某些字符不够就停止收缩记录当前窗口作为候选答案。这些判断都必须在移动左指针之前完成顺序反了就会得到错误的边界。第三Java的String是immutable的频繁substring会产生大量String对象最好记录起始索引和长度最后再截取一次。这道题如果不用这个方法在超大用例上会明显变慢。2.5 字符串的排列LeetCode 567与438几乎同源的套路题这题是“字符串的排列”给定s1和s2判断s2是否包含s1的某个排列。本质上跟438一模一样在s2中找一个长度等于len(s1)的子串使它的字符频率与s1完全一致。理解了438这道题可能只需要五分钟就能写出来。它唯一的差别是438返回所有位置567只返回是否存在。我建议把438和567放在一起刷你会发现它们的框架完全相同唯一的差别就是答案采集的位置。把这两道题吃透你对“固定窗口 频率数组 匹配判断”的组合会建立肌肉记忆后面遇到任何“异位词”类的变体都能快速反应。3. 滑动窗口最大值双端队列与单调队列的进阶技巧如果说前面的题目是“双指针 窗口内状态”那“滑动窗口最大值”LeetCode 239就是另一个维度的问题了。它的题干是给定数组有一个大小为k的滑动窗口从左向右移动求每次窗口内的最大值。朴素做法每个窗口用O(k)时间找最大值总复杂度O(nk)n和k都能到10⁵时直接超时。3.1 朴素解法与优先级队列为什么不行第一反应可能是用大根堆PriorityQueue维护窗口内元素每次取堆顶就是最大值。但Java的PriorityQueue不支持高效地删除指定元素——remove(Object)是O(k)的当窗口每次移动都要删除left指向的元素时整体复杂度又退化成了O(nk)。更麻烦的是堆顶是动态变化的删除非堆顶元素后堆的结构调整也需要O(log k)但定位元素本身就已经O(k)了这个开销在大数据量下完全不可接受。所以需要换一种思路我们真的需要“维护窗口内所有元素”吗不我们只想知道窗口内哪个元素是最大的。如果一个元素比它左侧的元素大那左侧那个元素在窗口内就没有任何机会成为最大值了——因为它比新来的元素小而且它还会比新元素先离开窗口。3.2 单调双端队列的设计思路与Java实现基于上面的观察可以维护一个单调递减的双端队列deque队列里存的是元素的下标时刻保证队头元素是当前窗口内的最大值。具体规则是移除队头已经不在窗口内的下标即下标小于等于left-1的从队尾依次弹出所有值小于等于当前新元素的元素下标因为它们在窗口内永远不会成为最大值将当前元素下标加入队尾队头元素就是当前窗口的最大值。为什么从队尾弹出的是“小于等于”而不是“小于”因为如果相等旧的元素在窗口内的“生存期”比新元素短更靠左保留旧元素没有意义弹出后让新元素顶上可以避免相等值带来的窗口边界判断麻烦。Java实现public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] res new int[n - k 1]; DequeInteger deque new ArrayDeque(); int idx 0; for (int right 0; right n; right) { // 移除窗口外的元素 while (!deque.isEmpty() deque.peekFirst() right - k) { deque.pollFirst(); } // 保持队列单调递减从队尾弹出不大于当前值的元素 while (!deque.isEmpty() nums[deque.peekLast()] nums[right]) { deque.pollLast(); } deque.offerLast(right); // 窗口形成后队头就是最大值 if (right k - 1) { res[idx] nums[deque.peekFirst()]; } } return res; }这里的Deque接口在Java里推荐用ArrayDeque实现性能优于LinkedList。注意第一个while循环的条件是peekFirst() right - k因为当窗口移动到right时窗口内允许的最小下标是right - k 1所以下标为right - k及以前的元素都已经离开窗口。如果写成 right - k 1逻辑等价但不够直观我习惯写成 right - k。3.3 复杂度分析与算法正确性证明思路每个元素最多被加入队列一次、弹出队列一次因此总复杂度O(n)空间O(k)。正确性证明的思路是反证法假设某个元素x在某个窗口内是最大值但x不在队列中。那么x一定是在加入时被某个值大于等于x、且下标在x右侧的元素y弹出。当窗口滑到包含x和y的某个位置时y一定还在窗口内且y x这与x是最大值矛盾如果相等取y同样正确。因此队头元素必然是该窗口的最大值。这个证明思路面试时如果能讲出来会是不小的加分项。4. 进阶题型与常见误区滑动窗口不是万能药刷完基础题之后你会发现很多题目喜欢在滑动窗口上叠加其他知识点让本来清晰的题目变得复杂。这里我挑两个高频变体和三个我见过最多的误区讲一讲。4.1 滑动窗口 vs 双指针到底什么时候该用谁这两个概念经常被混用实际上它们有微妙的差别。双指针更强调“两个指针分别从两端向中间移动”或者“一个快指针一个慢指针”解决的往往是“寻找满足条件的点对”问题滑动窗口则一定是连续区间重点在于维护窗口内状态。判断标准很简单如果题目要求的是“连续子数组/连续子串”就用滑动窗口如果题目要求的是“两个元素的组合”就用双指针。举个例子“三数之和”是双指针“无重复字符的最长子串”是滑动窗口两者差别一目了然。4.2 窗口内状态的存储选择HashSet、数组还是HashMap在Java里这个选择很影响代码的简洁性和性能。如果题目涉及的字符集是ASCII直接int[128]是最快的连HashSet都不用如果只涉及小写字母int[26]更节省空间如果涉及的字符范围不定用HashMap更通用。我见过很多人在处理“最小覆盖子串”时明明是小写字母却用HashMap代码写得很冗长还容易漏key的判断。虽然是同一个思路但数据结构的选型直接决定了代码的可读性和面试的形象分。4.3 频繁踩坑的边界条件滑动窗口的边界问题是重灾区。第一个坑是“窗口还没形成时不能更新答案”比如固定窗口大小k在right k - 1时窗口还没满这时候取窗口状态只会得到错误结果。第二个坑是“左指针不能越过右指针”在收缩时如果left一直加到等于right说明窗口已经空了再继续加会数组越界。第三个坑是“更新答案的时机”——是收缩之前还是收缩之后取决于答案要求的窗口是否必须满足某个条件。我把这类边界整理成一个速查表刷题前看一遍能少踩很多坑。场景常见错误修正方法固定窗口大小窗口未满就记录答案结果偏小或漏解等right k - 1再记录收缩左指针时导致left right数组越界收缩条件加left right在收缩前记录答案但答案应取收缩后窗口结果包含非法窗口先收缩后更新答案使用Integer缓存比较相等值大于127时相等判断失败用intValue()或直接比较int窗口哈希表未移除已离开窗口的字符统计失真左指针移动时同步更新频率表4.4 滑动窗口的局限什么时候不能用滑动窗口滑动窗口看起来万能但它的前提是窗口收缩后能恢复到收缩前的状态。比如“乘积小于k的子数组”这类题窗口内乘积在收缩时可以直接除以移出元素状态可以恢复可以用滑动窗口但如果约束条件是“窗口内所有元素互不相同且和为奇数”这种“非幂等”条件移出元素后历史状态无法简单恢复滑动窗口就失效了。这种情况下可能需要用前缀和、线段树或分治等思路。面试时如果盲目套滑动窗口模板很容易在不可行的问题上浪费大量时间。我的建议是拿到题先问自己两个问题——这个题目要求的是连续区间吗这个区间状态的变化是可逆的吗两个答案都是“是”再放心用滑动窗口。5. 面试实战如何把滑动窗口答成加分项最后一章我聊聊面试技巧。刷题和面试确实是两回事很多人LeetCode刷了三百道面试时还是说不清楚思路。滑动窗口这类“模型固定”的题目其实是面试中最容易拿到沟通分的题型。5.1 和面试官的沟通套路先把“不可能”讲清楚面试官抛出滑动窗口题目时不要上来就写代码。先用两句话说清楚暴力解法的局限再提滑动窗口的优化思路。这两句话的模板我都替你想好了“这题暴力法是枚举所有起点和终点时间复杂度O(n²)。因为目标是连续子数组而且窗口向右扩展时状态可以增量更新所以可以用滑动窗口把复杂度降到O(n)。”这句话说完面试官基本就知道你懂这题了。5.2 滑动窗口高频追问list与必背答案面试官喜欢追问的细节主要有三类第一为什么while收缩而不是if答案是因为要持续满足条件收缩次数可能不止一次。第二时间复杂度为什么是O(n)而不是O(n²)因为left和right总共移动O(n)次。第三如果窗口内状态用HashMap维护空间复杂度是多少最坏情况下窗口大小n所以是O(n)。这三个问题能对答如流面试官会认为你是真正理解的。5.3 时间不够时的刷题策略Top100里的优先级排序如果备战时间紧我建议优先刷这几道LeetCode 3无重复字符的最长子串、LeetCode 209长度最小的子数组、LeetCode 76最小覆盖子串。这三道是滑动窗口的三座大山覆盖了所有核心技巧——可变窗口、固定窗口、哈希表状态维护和复杂条件判断。时间充裕再刷LeetCode 239滑动窗口最大值和LeetCode 438找到字符串中所有字母异位词前者练单调队列后者练固定窗口的频率对比。这五道题吃透Top100里的滑动窗口部分就稳了。提示刷题时不要只看题解至少自己手写三遍。第一遍看着模板写第二遍默写第三遍不看任何提示直接写。三遍之后你会发现滑动窗口的框架已经内化成你的思维定势了。这个方法听着笨但效率非常高。我个人在实际刷题和面试中最大的体会是滑动窗口这类题本质上是在考“状态维护的纪律性”。你不需要多天才的算法灵感你需要的是精确地控制左右指针精确地维护窗口里每一份状态精确地选择答案的更新时机。这些“纪律”通过刻意练习完全能获得。如果你在刷题时感觉某个滑动窗口的题总是差一点点别急着看题解先检查左指针有没有正确收缩、答案更新时机对不对、窗口状态有没有及时移除离开的元素——八成的问题都出在这三个地方。