滑动窗口这块内容我在力扣上反复刷了三轮才算是真正搞明白。第一次是照着题解抄抄完就忘第二次是自己硬写写出来的代码又长又臭到了第三轮我才摸到这套解法的门道。回头看滑动窗口真不算难难的是你什么时候能想到用它、以及怎么把窗口收缩的边界条件理清楚。这篇复盘就把我踩过的坑、总结出来的模板、还有几个经典题的拆解一次性说透希望能帮你少走点弯路。1. 滑动窗口到底在解决什么问题1.1 先从暴力解法的痛点说起先想一个最简单的场景给定一个数组和一个目标值找出数组中和大于等于目标值的最短连续子数组。如果你不看任何算法技巧第一反应肯定是暴力枚举——把所有连续子数组都找出来分别求和筛出符合条件的再比谁最短。这个思路没错但复杂度是 O(n²)。数组长度一上来比如十万、百万级别基本就跑不动了。你可能会说可以加个前缀和优化把求和变成 O(1)但枚举子数组本身还是 O(n²)总复杂度没变。滑动窗口解决的正是这一类连续子区间 最值或计数的问题。它的核心想法很简单窗口的左右边界都只往前走不回退。右边界负责扩张把新元素纳入窗口左边界负责收缩把不再符合条件的元素踢出去。整个过程像一条毛毛虫在数组上爬头往前走尾跟上一次遍历就能做完。这一下把 O(n²) 降到了 O(n)。别小看这个优化实际刷题时很多看似是子数组的题目只要让你求的是连续区间的某个性质大概率就是滑动窗口的菜。1.2 什么样的题一眼就能认出是滑动窗口这是我刷题最大的收获之一学会识别题型比记住解法更重要。我把能套滑动窗口的题分为两类你在读题时留意这几组关键词就好。第一类题目里明确出现了连续子数组subarray或连续子串substring并且要求你求满足某个条件的最长、最短或数量。比如无重复字符的最长子串、和大于等于 target 的最短子数组、至少有 K 个重复字符的最长子串。第二类题目给你一个固定长度的窗口让你在这个窗口里求最大值、最小值、平均值之类的统计量。比如大小为 K 的窗口的最大和、滑动窗口最大值这道题力扣标 Hard但只要掌握了单调队列的思路其实挺套路的。换句话说只要问题涉及连续区间而且区间的端点移动是有方向的往右走滑动窗口基本都能上。如果区间可以任意乱序、或者让你求的是离散元素的组合问题那就该想别的招了。判断标准我记得很牢连续 区间 最值/计数 → 优先想滑动窗口。2. 一套模板吃透滑动窗口2.1 可变窗口的标准骨架滑动窗口的代码写多了之后你会发现它就是一个固定的骨架往里面填空就行。我整理了一个通用模板Python 和 Java 都能套先给你看 Python 版本def sliding_window(nums, k): n len(nums) left 0 window {} # 或者用数组/变量维护窗口状态 result 0 for right in range(n): # 1. 扩张窗口把 nums[right] 纳入窗口 window[nums[right]] window.get(nums[right], 0) 1 # 2. 收缩窗口不满足条件时left 右移 while not condition(window): window[nums[left]] - 1 if window[nums[left]] 0: del window[nums[left]] left 1 # 3. 更新答案此时窗口满足条件记录结果 result max(result, right - left 1) return result这个模板的关键在于三件事什么时候扩张、什么时候收缩、什么时候更新答案。很多初学者死记模板却搞不懂这三步的顺序一换题就懵。我的经验是先想清楚窗口满足什么条件再想什么时候需要收缩。比如无重复字符的最长子串条件是窗口内所有字符都不重复当右边界加进来的字符导致重复时就要收缩左边界直到重复消失。收缩完成后窗口自然满足条件此时窗口长度就是一个可行解更新答案即可。2.2 固定窗口的思路差异固定窗口稍微有点不一样。固定窗口的意思是窗口长度从一开始就是确定的比如每个长度为 k 的子数组的最大和你不需要条件判断去收缩窗口只需要在窗口大小超过 k 时left 跟着 right 一起往前走。def fixed_window(nums, k): n len(nums) left 0 window_sum 0 result 0 for right in range(n): window_sum nums[right] # 扩张 if right - left 1 k: # 窗口超长收缩 window_sum - nums[left] left 1 if right - left 1 k: # 窗口恰好 k 长度更新答案 result max(result, window_sum) return result固定窗口的套路更简单扩张、超长收缩、恰好长度更新。不用 while用 if 就行因为每次右指针移动一格窗口最多超长一格。不过我这里要特别提醒一点可变窗口和固定窗口的核心区别在于收缩条件。可变窗口的收缩条件通常跟题目要求有关比如无重复、和的大小固定窗口的收缩条件只有一个就是窗口长度超了。你做题之前先判断是哪种再套模板正确率会高很多。3. 必刷经典题拆解从最长无重复到最小覆盖3.1 无重复字符的最长子串LeetCode 3这道题可以说是滑动窗口的入门必修课。题目不难但信息量很大。给定一个字符串 s找出其中不含重复字符的最长子串的长度。我的解题思路是这样用一个字典 window 记录每个字符在窗口内出现的次数right 指针遍历整个字符串每遇到一个字符就加进窗口。加进去之后如果这个字符的出现次数大于 1说明窗口内有重复那么 left 就右移同时把移出窗口的字符计数减一直到重复消除。def lengthOfLongestSubstring(s: str) - int: left 0 window {} result 0 for right in range(len(s)): c s[right] window[c] window.get(c, 0) 1 while window[c] 1: d s[left] window[d] - 1 left 1 result max(result, right - left 1) return result注意这里的 while 条件是当前字符出现次数大于 1而不是窗口内有任意重复字符。这两种写法等价但前者判断起来更直接因为你只需要盯着刚加入的字符就行。我一开始在这个地方犯过糊涂想着要不要每个字符都检查一遍有没有重复。后来想明白了窗口内本来是没有重复的加入新字符后如果产生了重复那一定是新字符带来的。所以只需要判断新字符的计数是否大于 1 就够了。3.2 长度最小的子数组LeetCode 209这道题是滑动窗口的另一个经典入门题和上面那道一左一右正好对应最短和最长两种方向。题目给定一个正整数数组 nums 和一个正整数 target找出该数组中满足其和大于等于 target 的长度最小的连续子数组并返回其长度。思路正好反过来right 扩张加和窗口内的和一旦大于等于 target满足条件就尝试收缩左边界看看能不能在仍然满足条件的情况下让窗口更短收缩到不满足为止然后记录收缩前的长度。def minSubArrayLen(target: int, nums: List[int]) - int: left 0 window_sum 0 result float(inf) for right in range(len(nums)): window_sum nums[right] while window_sum target: result min(result, right - left 1) window_sum - nums[left] left 1 return result if result ! float(inf) else 0注意这里有个细节更新答案要放在收缩循环里面而不是收缩完成后。因为收缩完成时窗口已经不再满足条件了你记录的是最后一次满足条件的长度。很多人写这道题的时候会把 result 的更新写在 while 外面结果发现求出来的不是最短长度而是最短长度加一或者其它奇怪的值。这个坑我踩过印象特别深。记住一句话保证窗口满足条件的时候才去更新答案如果窗口本身已经不满足条件了更新出来的数据一定不对。这两道题一对比你就能琢磨出滑动窗口的度一道是窗口内出现异常就收缩到正常另一道是窗口内满足了就试试能不能再缩小。方向相反但骨架完全一致。3.3 最小覆盖子串LeetCode 76这道题是 Hard 难度但用滑动窗口加计数器其实不难。题目要求给你一个字符串 s 和一个字符串 t返回 s 中涵盖 t 所有字符的最小子串。这里的难点在于你怎么判断涵盖了 t 的所有字符。我的方案是维护一个 need 字典记录 t 中每个字符需要的次数再用一个变量 need_cnt 记录还有多少种字符没满足。def minWindow(s: str, t: str) - str: from collections import Counter need Counter(t) need_cnt len(need) left 0 result min_len float(inf) for right in range(len(s)): c s[right] if c in need: need[c] - 1 if need[c] 0: need_cnt - 1 while need_cnt 0: if right - left 1 min_len: min_len right - left 1 result s[left:right1] d s[left] if d in need: if need[d] 0: need_cnt 1 need[d] 1 left 1 return result核心逻辑need_cnt 归零说明所有字符类型都齐了此时窗口是一个可行解。尝试收缩左边界如果左移的字符恰好是某个需求已经满足的字符need_cnt 就要加一意味着这种字符不够了循环退出继续扩张右边界找下一个可行解。这道题的启发在于窗口的条件不一定是一个简单的计数它可以是一个多字段的字典。你只要保证条件判断和收缩逻辑是同步更新的窗口就能始终维持正确状态。我做题时发现很多同学把 Hard 题想得太复杂其实力扣的 Hard 题放在滑动窗口这个标签下大部分都是套模板 状态多维护一些的模式没有想象中那么难。4. 进阶技巧滑动窗口 单调队列4.1 为什么普通滑动窗口搞不定最大值如果题目只是让你求窗口内元素的和那用一个变量就能搞定。但如果让你求的是窗口内的最大值而且窗口是滑动着的问题就来了窗口滑走一个元素你怎么知道剩下元素的最大值是多少最笨的办法是每次扫描一遍窗口那样复杂度是 O(n×k)k 是窗口长度。要是 k 接近 n复杂度又退化成了 O(n²)这就失去了滑动窗口的意义。解决办法是在滑动窗口基础上引入一个单调队列deque专门用来维护窗口内的最大值。队列里的元素按照从大到小的顺序排列队首就是当前窗口的最大值。4.2 单调队列的实现细节LeetCode 239 这道题是滑动窗口 单调队列的经典代表。题目给你一个整数数组 nums 和一个滑动窗口大小 k找出所有滑动窗口里的最大值。我的做法是维护一个双端队列队列里存的是元素的下标而不是元素本身。为什么存下标因为下标能告诉我们队列里的元素是否还在窗口内方便过期淘汰。新元素入队时先弹出所有值比它小的队尾元素再把新元素下标压入队尾。队首元素如果已经滑出窗口下标小于等于 i-k就弹出。from collections import deque def maxSlidingWindow(nums: List[int], k: int) - List[int]: dq deque() result [] for i in range(len(nums)): # 新元素入队弹出队尾所有比它小的元素 while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) # 队首元素滑出窗口弹出 if dq[0] i - k: dq.popleft() # 窗口满 k 个记录答案 if i k - 1: result.append(nums[dq[0]]) return result为什么要把比新元素小的队尾元素全部弹出因为只要这些更小、更老的元素还在窗口里新元素永远比它们有资格当最大值一旦它们滑出窗口新元素可能还留在窗口里。所以它们注定永远不会成为窗口最大值留之无用。我一开始写这道题时队列里存的是元素值结果在判断队首是否过期的时候总是出问题。后来改成存下标逻辑一下就顺了。这里也分享给大家涉及是否在窗口内的判断时队列里存下标是更稳的做法。5. 常见问题与排查技巧实录5.1 死循环问题left 没动滑动窗口最容易出的 bug 是死循环具体表现是 right 一直在扫描但 left 不往前走while 循环里判断条件永远为真程序卡死。这种 bug 十有八九是收缩分支里忘了处理窗口数据。比如你用字典维护窗口left 右移时只做了left 1没把window[nums[left]]减掉。那窗口内数据一直是旧的条件永远满足不了left 卡在原地。排查思路很简单在 while 收缩循环里打印窗口状态看看 left 移动前后窗口内的计数有没有同步变化。我之前排查一个问题时发现窗口内的计数比实际元素数还大好几根指针错位就是收缩分支少写了一行。5.2 边界条件窗口初始化和空输入力扣的用例永远比你想的刁钻。空数组、空字符串、k 大于数组长度、target 是 0、数组里有负数……每一个边界条件都可能让你的代码暴毙。拿 209 那题来说如果 target 是 0while window_sum target 永远为真left 会一路狂奔到数组末尾最终 output 0。但题目说 target 是正整数所以还好。可如果你是拿这道题练手最好在代码开头加一个if not nums: return 0的防御。别觉得加防御判断丢人。力扣评论区都是比谁代码短但日常工程里你写的算法迟早要处理脏数据。先把边界处理干净再谈优化。5.3 别忘了更新答案的位置这个问题太典型了以至于我想单独拿出来说。很多滑动窗口题的解法都长得很像但答案更新的位置各不相同。有些题在收缩完成后更新有些题在收缩过程中更新有些题在每次 right 移动后更新。判断标准只有一个你更新答案时窗口状态是否一定是合法的209 那题窗口收缩后不合法了所以必须在收缩循环内更新3 那题窗口收缩后一定合法了所以可以在收缩循环外更新。遇到新题时先问自己这个问题答案的更新位置就清楚了。我在刷题过程中发现很多人的代码逻辑都对了就是答案位置放错导致结果偏执这一条是最常见的低级错误。5.4 字典计数 vs 数组计数性能差距如果窗口里的元素是字符串字符用字典没问题。但如果元素是整数而且你知道取值范围比如 0 到 100用数组当计数器会比字典快一个数量级。# 假设元素范围是 0~100 count [0] * 101 # 添加 count[val] 1 # 删除 count[val] - 1数组访问是 O(1) 且常数极小字典虽然也是 O(1)但哈希运算的常数大很多。力扣刷题时一道题如果时间卡得紧把字典换成数组往往能救你一命。华为 OD 机试那种环境尤其如此时间卡得很死性能优化不能不做。5.5 一个实用的自测技巧写完代码别急着提交先用小样例手跑一遍。我个人的习惯是拿一个nums [1, 3, -1, -3, 5, 3, 6, 7], k 3这种样例手动推演一遍窗口的变化过程把每一步的 left、right、窗口状态、答案都写出来再和自己的代码对比。这个习惯帮我提前发现了很多逻辑错误省了不少提交失败的尴尬。刷题讲究的是手感手感就是靠这种反复手推积累起来的。6. 我的实战心得与后续做题建议这个章节我想跟你分享一些超脱具体题目的思考。滑动窗口不是一个孤立的知识点它其实是双指针技巧在连续区间问题上的应用理解它的本质对你做其他题会有帮助。双指针的核心思想是利用数据的单调性减少不必要的遍历。滑动窗口依赖的单调性是随着右指针向右移动窗口覆盖的区间只会变大窗口内元素只会变多。所以当你把一个元素纳入窗口后就不需要回头再处理它了每个元素最多被处理两次进一次出一次这才有了 O(n) 的复杂度保证。理解了这个本质很多变体题你就知道怎么做了。比如含有最多两个不同字符的最长子串、每个元音包含偶数次的最长子字符串这题还牵扯到状态压缩比较进阶等等核心都是维护一个窗口状态然后按模板走。做完了力扣的滑动窗口标签题我还推荐你去看看前缀和 哈希表的组合。这两兄弟经常交替出现有些题看起来像滑动窗口其实是前缀和做的有些题用滑动窗口反而别扭换前缀和一下就顺了。这里我不展开但建议你刷题时把它们放在一起对比着学。最后分享一个小技巧。如果你刷了一会儿滑动窗口的题觉得头晕脑胀别硬扛。打开记事本画一条线段代表数组用两个游标模拟 left 和 right亲手推一遍窗口的变化过程。这个简单的动作比你看十道题解都管用。我刷 LeetCode 239 的时候就是用这个方法一步步推才彻底弄懂了单调队列为什么能保持队首是最大值。动手永远比动眼有效。