我最早被滑动窗口绕晕不是因为代码写不出来而是没想明白一个问题为什么看起来是两个 while 套在外面、里面再塞一个 for 的写法复杂度居然是 O(n)而不是 O(n²)后来刷的题多了才反应过来滑动窗口本质上不是一套复杂的算法而是一种「怎么省掉重复计算」的思维方式。它解决的是连续子数组、连续子串这一类问题核心特征就一句话右边界往前走左边界跟着走窗口里的信息被持续复用不回退。这篇东西我不打算按教科书的方式给你列定义、推公式。我会直接从一道最经典的题切入讲清楚为什么需要它、它到底省在哪再把定长窗口、可变窗口、单调队列、计数收缩这些常见玩法一个个拆开。最后会聊几个特别容易翻车的地方包括很多人分不清的「滑动窗口滤波」和算法里的滑动窗口到底是不是一回事。如果你正在刷题准备面试或者工作中遇到子数组、子串统计、区间最值这类需求这篇文章应该能帮你把这一整块知识串起来。1. 先从一道最经典的题说起为什么需要滑动窗口滑动窗口最常见的应用场景是处理「连续区间上的统计问题」。什么叫连续区间数组里下标 2 到 8 这段元素字符串里第 3 个到第 10 个字符这些都是连续区间。算法题里有一大类问题都是围绕这种区间来的求区间和、求区间最大值、求区间内有多少种不同的字符、求满足某个条件的最短/最长区间等等。直接上一道几乎所有刷题人都见过的题给定一个字符串 s找出其中不含有重复字符的最长子串的长度。如果没见过这道题你一上来最自然的想法肯定是暴力枚举所有子串逐个检查里面有没有重复字符。伪代码大概是这样的def length_of_longest_substring(s: str) - int: n len(s) ans 0 for i in range(n): for j in range(i, n): # 检查 s[i:j1] 是否有重复字符 if has_unique_chars(s, i, j): ans max(ans, j - i 1) return ans这个做法的时间复杂度是 O(n³)——枚举所有子串是 O(n²)每次检查是否重复又是 O(n)。n 小的时候无所谓n 到几千就明显吃力了leetcode 上直接超时。但是你会发现一个问题大部分的重复检查是没有意义的。假设你已经知道 s[2:8] 这个窗口是符合条件的、没有重复字符接着要判断 s[2:9] 是否符合条件时暴力的做法是重新把 s[2:9] 里每个字符扫一遍哈希表。这完全没有必要因为 s[2:8] 的信息你已经算过了只需要检查新加进来的 s[9] 有没有和窗口里的字符冲突就行了。这就是滑动窗口的出发点不要每次都从头开始而是维护一个区间往右移动的时候只处理边界上的变化。同样是这道题用滑动窗口的思路就是右边界一个一个往右走每走一步就把新字符「加入窗口」如果发现当前窗口里有重复字符左边界就往右收缩直到重复消失。整个过程左边界从左往右走一次、右边界也从左往右走一次每个字符最多被访问两次复杂度 O(n)。我把暴力解和滑窗解放在一起对比方案需要枚举的区间数每个区间的额外检查总复杂度暴力枚举O(n²) 个子串每次 O(n) 查重O(n³)滑动窗口左右指针各扫一遍每次 O(1) 更新O(n)看到差距了吧。暴力是 n 的三次方滑窗是线性。从 O(n³) 到 O(n)这不是「优化了一点点」这是从没法用到随便跑的区别。n 10⁵ 的时候O(n³) 基本等于算到天荒地老O(n) 一瞬间就出结果了。这个例子还引出了滑动窗口最重要的一个直觉它把「从零开始扫一个区间」变成了「只处理区间两端变化的那一点点地方」。这正是所有滑窗类问题的灵魂。2. 窗口为什么能省钱不回溯的双指针与均摊复杂度秘密说完为什么要用接下来得说清楚它为什么快。很多初学者能背出滑动窗口的模板但对复杂度一脸懵明明里面套了 while凭什么说是 O(n)关键在于滑动窗口里的两个指针全程只往一个方向移动从不回退。左指针不会右移几步之后又跳回左边重新开始右指针更不会来回抖动。这个特性在算法里有个专门的说法叫「双指针的单向移动」正是这个单向性保证了总操作次数是可控的。我来做一次严谨的均摊分析。假设数组长度是 n右指针从 0 走到 n最多移动 n 次左指针在 while 循环里从 0 走到 n也最多移动 n 次。就算 while 循环每次都要执行左右指针加起来的移动总量也就 2n。窗口内每次更新数据结构的成本如果是 O(1)那整个算法就是 O(n)。注意这里的 O(n) 是「均摊」出来的不是说每一步都只用常数时间。有可能某一步窗口特别长while 一收缩就缩掉了几十个元素但这几十个元素之前是右指针花了几十步才加进来的现在被左指针一次性清出去。你欠下的复杂度迟早要还但还一次也就一次。这就是均摊分析的通俗理解把左指针的总移动次数和右指针的总移动次数加起来算总账而不是看某一步的局部开销。网上有一种常见的错误说法是「因为左右指针各移动 n 次所以是 2n所以 O(n)」。这句话方向对但不够精确。更准确地说关键在于「每个元素最多被加入窗口一次、被移出窗口一次」再加进来的时候之前的被移出操作已经把信息处理好了。我打个比方。想象一个传送带上面一个一个地输送包裹你两只手框住一段传送带上的包裹这段就是窗口。你检查包裹是否合格合格的留在手框里不合格的从手框里扔到旁边废品堆。右手右边界负责把新包裹放进手框的右侧左手左边界负责把不合格的包裹从手框左侧挪出去。两只手只能往右移动不能往回退着找已经看过的包裹。你总共扫完所有包裹两只手各自最多走了传送带那么长的距离检查动作加起来也是线性的。那你可能会问为什么不能像二分查找那样把左指针直接跳到 mid 呢因为滑动窗口处理的问题不存在排序数组那样的单调性保证你无法通过「窗口中间某处不符合条件」推断出「窗口左半边全部不符合条件」。左指针老老实实逐步右移反而是最稳妥、最能保证不漏解的做法。搞懂了这个底层机制你后面写代码遇到任何「为什么这里能 break / 为什么复杂度没问题」的疑惑都可以回到这个原则来判断看看当前算法的指针是否满足单向移动如果不满足那它很可能不是真正的滑动窗口。3. 定长与可变长两类窗口框架与代码模板滑动窗口在实际应用里大致分成两类定长窗口和可变长窗口。它们的代码骨架略有不同但底层的「右进左出、动态维护」思路是完全一致的。我建议你把这两套模板都背到肌肉记忆刷题的时候能省很多力气。3.1 定长窗口右进、判断、左出定长窗口一般出现在「窗口大小固定为 k求窗口内某统计量」这种题。典型代表是给定数组和窗口大小 k求每个窗口的最大值、最小值、平均值或者满足某种条件的窗口个数。代码模板参考下面这段def fixed_window(nums, k): n len(nums) # 先初始化前 k 个元素第一个窗口 window ... for i in range(k): add(window, nums[i]) # 处理第一个窗口的结果 ans evaluate(window, ...) # 然后窗口整体右移每次移一格 for i in range(k, n): # 右边进一个新元素 nums[i] add(window, nums[i]) # 左边出一个旧元素 nums[i-k] remove(window, nums[i-k]) # 处理当前窗口的结果 ans best(ans, evaluate(window, ...)) return ans注意这里的关键点add 和 remove 的顺序。一定是先加右边的、再删左边的这样窗口的主体始终是连续的、长度固定为 k。如果用 remove 在 add 之前操作边界情况会多出一些窗口中间有洞的诡异状态自找麻烦。3.2 可变长窗口右进、收缩、再更新可变长窗口解决的是一类「求满足某个条件的最长/最短连续区间」的题。经典如无重复字符最长子串、最短覆盖子串、最长连续 1 的个数允许翻转 k 个 0等。模板长这样def variable_window(arr): n len(arr) left 0 state empty_state # 用来记录窗口内的统计信息 ans 0 for right in range(n): # 1. 右边元素进窗口更新统计 add(state, arr[right]) # 2. 窗口不满足条件时左边界收缩 while not condition(state): remove(state, arr[left]) left 1 # 3. 此时窗口满足条件更新答案 ans max(ans, right - left 1) return ans这个模板的精髓在于「收缩条件」。注意 while 循环的判断条件是「窗口不满足题目要求」时收缩。比如最长无重复子串不满足的条件是「窗口内存在重复字符」那就一直 shrink 到没有重复为止。比如最短覆盖子串不满足的条件是「窗口还没覆盖到模板串的所有字符」那就不断把左边界往右推直到窗口依然覆盖、但已经不能再缩了。还有一个容易犯错的地方答案是应该在收缩前更新还是收缩后更新其实这取决于题目问的是「满足条件的最长区间」还是「满足条件的最短区间」。求最长收缩前更新因为收缩会把区间变短收缩后更新拿到的长度大概率不是最优。求最短收缩后更新因为刚收缩完的窗口是「当前右边界下最逼近边界条件的一次」。这一点当初也坑了我好一阵。做「尽可能使字符串相等」这类题的时候我一开始在 while 循环外更新答案结果某些测试用例过不了。后来才总结出规律先确定题目的目标是「尽量长」还是「尽量短」再决定答案更新的时机。这个细节面试的时候尤其容易被问。3.3 一个完整的实战例子最小覆盖子串光说模板太抽象我拆一道真正能体现可变长窗口威力的题——最小覆盖子串。题目大意给定字符串 s 和 t在 s 中找出包含 t 所有字符包括相同字符出现次数的最短子串如果找不到就返回空串。思路是这样的先统计 t 里每个字符的出现次数存在一个字典 need 里然后右指针逐个扫描 s遇到 t 里的字符就把它在窗口里的计数加一同时用一个变量 matched 记录「已经满足数量要求的字符种类数」。当 matched 等于 need 里 key 的数量时说明当前窗口已经覆盖了 t此时开始收缩左边界尝试把窗口压到最短。def min_window(s: str, t: str) - str: need {} for ch in t: need[ch] need.get(ch, 0) 1 left 0 matched 0 # 满足数量要求的字符种类数量 start 0 min_len float(inf) window {} for right, ch in enumerate(s): # 右进 if ch in need: window[ch] window.get(ch, 0) 1 if window[ch] need[ch]: matched 1 # 收缩当前窗口已经覆盖 t 的所有字符 while matched len(need): if right - left 1 min_len: min_len right - left 1 start left # 左出 left_ch s[left] if left_ch in need: if window[left_ch] need[left_ch]: matched - 1 window[left_ch] - 1 left 1 return if min_len float(inf) else s[start:start min_len]这段代码里有几个细节值得反复琢磨。matched 变量的作用不用每次遍历整个 need 字典而是用一个计数器实时跟踪把条件判断降到 O(1)。这是滑动窗口里一个很常用的优化技巧。只有 t 里的字符才需要记录计数s 里其他字符进窗口不需要任何处理因为它们不影响「是否覆盖」的判断只影响窗口长度。收缩的时候必须先判断 left_ch 是不是 need 里的字符再决定怎么更新 matched。这个顺序一旦错了matched 的计数就会错乱结果就跟着错。这段代码我觉得是可变窗口里的典型搞懂这一道很多同类的「覆盖/包含」问题都能照着改写。4. 实战中的三种窗口维护策略哈希计数、单调队列和延迟更新窗口有了但窗口里的信息怎么维护才是区分不同层次的关键。同样是滑动窗口不同的统计需求要用不同的数据结构来配合。我按面试中出现频率从高到低整理三种最常见的维护策略。4.1 哈希表计数处理「种类、频次」类问题最常见的场景是「窗口里有哪几种元素、每种元素出现几次」。无重复字符最长子串、最小覆盖子串、字符串排列这类题核心都是窗口内字符的频次统计。操作是很直观的右指针进来一个元素就把它在 hashmap 里的计数加一左指针移除一个元素计数减一。减到 0 就删掉这个 key这样 len(hashmap) 就天然等于「窗口内不同元素的种类数」。有一个稍微反直觉的情况是什么时候应该用数组代替 hashmap如果字符集很小、确定比如只包含小写字母26 个直接用长度为 26 的数组会更快。因为 hashmap 有哈希计算的常数开销数组是 O(1) 纯下标访问。我在牛客上看到不少细节优化党都用这种数组写法实测在某些强数据下确实能快不少。freq [0] * 26 freq[ord(ch) - ord(a)] 1 # 右进 freq[ord(ch) - ord(a)] - 1 # 左出4.2 单调队列处理「窗口最值」问题如果要问的不是「窗口里有多长」而是「窗口里的最大值 / 最小值」那哈希表就帮不上忙了。你需要的是单调队列。最经典的题是求滑动窗口最大值。窗口每移动一格要快速返回窗口内的最大值。如果用普通办法每次求最大值都要遍历窗口 O(k)总复杂度 O(nk)k 大的时候照样超时。单调队列的思路是维护一个递减队列队头永远是当前窗口的最大值。每次新元素入队之前把队尾所有比它小的元素全部弹出因为它比它们都大、又比它们晚过期留着那些更小的元素已经没有意义了。然后队头如果已经滑出窗口下标小于 left也要弹出。from collections import deque def max_sliding_window(nums, k): n len(nums) dq deque() # 存的是下标方便判断是否过期 res [] for i in range(n): # 右边进把比当前元素小的全部弹出 while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) # 队头过期滑出窗口 if dq[0] i - k 1: dq.popleft() # 窗口形成开始记录答案 if i k - 1: res.append(nums[dq[0]]) return res这个写法的精妙之处在于队列里存的是下标而不是值。存下标有两个好处一是判断过期只需要比较下标二是即使值相同的元素也能通过下标区分先后不会误弹。很多初学者理解不了为什么弹出队尾更小的元素不会影响后续结果。我的理解方式是一个更小又更早过期的元素在它面前有一个更大又更晚过期的元素那这个小的元素永远不可能成为窗口最大值直接丢掉是安全的。单调队列里的「单调」本质上是在维护一种「淘汰」关系——淘汰掉那些既不强又活不久的候选者。4.3 延迟更新与累计变量处理「区间和、区间积」问题第三种比较朴素但极其常用窗口内的数值和或乘积不需要额外的数据结构用一个变量实时维护就行。区间和我们都知道右进的时候加一下左出的时候减一下。但有一个细节容易忽略如果数组里有负数单纯的「和值」并不具备单调性不能直接用 while 收缩的框架。比如求「和 target 的最短子数组」按直觉做是可行的因为正整数数组里随着窗口右移和是单调增加的但如果数组里有负数这个单调性就没了窗口加长并不一定让和变大这时滑动窗口的模板可能会漏解。这种情况需要换思路或者配合前缀和数组来处理。区间积也是类似。右进乘一下、左出除一下看起来很美但如果数组里有 0除数为 0 直接崩掉而且窗口内一旦出现 0整个乘积就是 0很难再通过乘除来维护。遇到含 0 的乘积题滑动窗口大概率不是最好的选择得考虑其他做法。这种维护策略的取舍我整理成了一张表格维护目标推荐工具适用场景坑元素种类/频次哈希表或定长数组子串覆盖、无重复、排列匹配更新顺序错乱导致计数不准窗口最值单调队列滑动窗口最大值/最小值忘了存下标导致过期判断失败区间和/积单个累计变量子数组和、连续乘积数组含负数或 0 时模板失效窗口本身只是一个框架真正的大头在于你用什么数据结构来维护窗口内的状态。面试的时候如果感觉自己思路对了但实现不出来多半是卡在了「维护策略」的选型上。5. 容易被忽略的变体和边界条件环形数组、恰好型问题和负数陷阱刷题刷到一定数量之后你会发现滑窗题目本身不难难的是各种变体和边界条件。这里挑几个最常踩的坑展开讲讲。5.1 环形数组把窗口搬上一条「环」先说环形变体。有些题目把数组头尾相接变成一个环然后求窗口内的最优值。比如「环形数组中的最大子数组和」「环形数组中的最长连续 1 的个数」这类题。处理环的套路非常统一把数组复制一份接在末尾然后用一个长度不超过 n 的窗口来做。这样环上的任意连续区间都能在这个 2n 长度的数组上找到对应的直线区间。但有一个隐藏的边界你要小心如果题目要求的区间长度不能超过 n比如环形数组的「最大子数组和」其实不是滑窗专属而是用 Kadane 算法那滑动窗口的 while 收缩条件里就必须带上长度约束。否则窗口可能越过环的起点把同一段元素算两次。# 环形数组里求长度为 k 的最大窗口和k n nums2 nums nums left 0 cur 0 ans -inf for right in range(len(nums2)): cur nums2[right] if right - left 1 k: cur - nums2[left] left 1 if right - left 1 k: ans max(ans, cur)这里面的关键判断是right - left 1 k一旦长度超过目标就立刻收缩。不用 while因为窗口长度是一格一格增长的超过一格只需要收缩一格。5.2 恰好型问题把「恰好」转化成「至多」第二个很容易卡的变体是「恰好」型问题。比如「数组中恰好包含 K 个不同整数的子数组个数」。这个「恰好」非常不友好因为滑动窗口天然擅长的是「至多」——窗口内不同整数不超过 K 个这个条件收缩起来很自然。处理「恰好」型问题的标准套路是恰好 K 至多 K - 至多 (K-1)。也就是求两个「至多」型结果然后相减。为什么这个转化成立因为「恰好有 K 种不同元素」的所有子数组可以看成「至多有 K 种」的子数组集合减去「至多有 K-1 种」的子数组集合。两个集合的差正好就是恰好 K 种的那部分。这个技巧在处理「恰好 K 个不同字符」「恰好 K 个奇数次数字」等题目时非常通用值得专门记下来。5.3 负数陷阱为什么数组有负数的区间和题不能直接贪心收缩第三个坑是负数。前面简单提过一次但值得单独展开。考虑「和 target 的最短子数组」这类题。在数组全为正数的情况下窗口向右扩展时和值单调递增所以一旦满足条件收缩左边界是安全的——因为继续往右扩展只会让和更大不会让窗口变短回到不满足状态。但如果数组里有负数这个逻辑就不成立了。可能窗口在 right10 时满足和 target收缩 left 到某处之后因为碰到了负数反而和值跌到 target 以下这时你可能得把 right 继续往右推好几个位置才能再次满足条件。窗口的右指针左指针都可能出现「走了又回头」的局面复杂度不再线性正确性也容易漏解。遇到这类题我的建议是优先切换思路要么用前缀和配合二分因为前缀和不依赖窗口元素的单调性要么看看题目暗示的数据范围是否允许其他做法。不要硬套滑窗模板套到最后很容易在某个负数的用例上报错。6. 面试和刷题中容易翻车的细节从过期判断到边界条件最后聊一些真正影响正确性的细节。这些细节单独看都挺小但凑在一起能把一份看起来正确的代码搞到测试用例一跑就崩。6.1 单调队列的「存下标」与过期判断单调队列里到底存下标还是存值如果只判断「当前最大值是谁」存值也够用但如果要判断「这个值是不是已经滑出窗口」就必须依赖下标。比如窗口右边界到 i 之后窗口范围是 [i-k1, i]那队头元素下标必须 i-k1否则就过期。这里有一个常见的错误写法用值相等来判断过期比如if dq[0] nums[i-k]。这个写法在元素值唯一的时候能碰对但一旦数组里有两个相同的最大值就会把不该弹出的元素弹掉。我见过不少面试者在白板编程时栽在这里。正确做法是队里存下标比较时用下标自带的过期条件彻底避开值冲突的问题。上面第 4 节那段代码就是这么写的建议直接背下来。6.2 可变窗口里答案更新的时机前面提过求最长和最短的更新时机不同这里再展开一下。其实「求最长」类型的题还有一个更微妙的点如果收缩条件设得不对可能会出现「窗口明明合法但已经被缩过头」的情况。比如求「最多有 K 个 0 的最长连续 1 子数组」很多人写的收缩条件是「窗口里 0 的数量 K」。这个判断本身没问题但如果在收缩完之后的代码里没区分「0 的数量刚好是 K」和「0 的数量小于 K」那答案更新的时候就会把一些并不满足题意的窗口长度记进去。稳妥的做法是严格遵循模板收缩条件就是「窗口违背题目要求」收缩结束后窗口一定满足条件然后在收缩结束后更新答案。不要试图自己发明收缩条件老老实实按「违背就缩」来写错误率能低很多。6.3 窗口为空的边界有些题在窗口收缩过程中可能把 left 推到 right 1导致窗口为空。比如最短覆盖子串当 s 和 t 没有交集时left 会一直往右走到超过 right。这时候如果你直接在收缩后访问 s[left] 就会越界。我踩过一次之后养成的习惯是每次收缩循环结束后都下意识检查一下 left 是否超过 right以及窗口长度是否为 0。这个习惯帮我避免了至少两三道题的白板翻车。6.4 与「滑动窗口滤波」的区别这部分放在最后是因为我觉得很有必要。热搜里经常能看到「滑动窗口滤波」「滑动窗口滤波延迟」「滑动窗口滤波 verilog」之类的词。每次有人搜进来我都挺担心他们把两个完全不同的东西混在一起。滑动窗口滤波Sliding Window Filter是数字信号处理领域的一个概念属于 FIR 滤波器的一种实现方式。它的基本思想是对一串信号用一个固定长度的窗口窗口内的样本做加权平均或其他运算每来一个新样本窗口整体往后挪一格。它在硬件verilog和嵌入式领域很常见解决的是信号平滑、去噪问题。而算法领域的「滑动窗口」Sliding Window Technique是双指针技巧的一种应用场景解决的是数组/字符串上连续区间的统计优化问题。虽然英文同名但它们的数学背景、应用场景、实现方式完全不一样。如果在搜索引擎上搜「滑动窗口」两拨内容会搅在一起很容易造成困扰。我的判断标准很简单如果题目和关键词里有「滤波器、时延、采样、FIR、verilog、平滑」那是信号处理如果和「子数组、子串、最长、最短、窗口最大值、覆盖、双指针」有关那是算法题。看准了再花时间别在错误的方向上浪费半天。6.5 实战中我还想额外提的两点第一点滑动窗口不是万能的。它只适用于「连续区间」问题而且窗口的统计信息要能支持 O(1) 或对数级地增删。如果维护成本做不到套滑窗反而会拖慢你的实现速度。第二点刷题的时候不要只看题解建议自己把第 3 节的两套模板抄下来、手写三遍特别是 fixed_window 和 variable_window 的边界条件手写和眼睛看完全是两种体验。我第一次在面试白板上写单调队列的时候因为没想清楚「存下标」这个点写着写着把自己绕晕了。从那以后我每次面到滑动窗口相关的题目第一件事就是先想清楚用什么数据结构维护窗口、要不要存下标、答案是收缩前更新还是收缩后更新。这三个问题想清楚代码基本就顺了。