★ FEATURED ARTICLE 1. 从暴力解到最优解滑动窗口到底解决什么问题先直接说结论滑动窗口不是一种神秘的高级算法它只是把“重复计算”这件事给砍掉了是一种对暴力遍历的优雅优化。在字符串、数组这类线性结构上凡是涉及“连续子串”“连续子数组”的最值、计数、包含关系问题你都应该本能地想到滑动窗口。为什么这样说因为我见过太多人一上来就背模板背完就忘遇到变体直接懵。问题不在于滑动窗口本身难而在于大家没有搞懂它产生的背景暴力做法到底慢在哪滑动窗口又是怎么绕开这个慢点的。举个例子给定一个数组求所有长度为K的子数组的最大和。最自然的暴力解法是把所有长度为K的子数组都遍历一遍累加求和然后取最大值。这个做法的时间复杂度是O(n*K)长度为n的数组共有n-K1个起点每个起点往后加K个数字。假设n是10万K是1万那就是10亿次加法。你仔细看这个过程会发现一个明显浪费第一个子数组累加了arr[0]到arr[9]第二个子数组只把区间移动了一位也就是arr[1]到arr[10]。但暴力做法又把arr[1]到arr[9]这9个元素重新加了一遍。这9个元素在上一轮明明已经算过一遍了完全没必要重新累加。滑动窗口的思路恰恰就是从这里切入的既然区间每次只挪动一步新的和 旧的和 - 离开窗口的数 新进入窗口的数。一次减法、一次加法整个区间的和就更新完了。这样一来原本需要O(K)时间的求和被压缩到了O(1)时间。整个过程只遍历一次数组时间复杂度从O(n*K)直接降到O(n)。这就是滑动窗口的核心逻辑用空间换时间也好用复用代替重算也罢本质上就是“记录状态、增量更新”。再往深一层说滑动窗口适合的问题通常满足两个特征。第一问题作用在一个线性结构上也就是数组或字符串。第二最终求解对象是连续的区间。你可以把滑动窗口理解成一把用左右指针圈出来的、不断移动的尺子这把尺子每一次移动都尽量利用上一次的结果而不是从零开始。这篇文章我会从最基础的窗口形态讲起逐步过渡到动态窗口、固定窗口再深入到需要配合哈希表、计数的经典问题最后给出完整的代码模板、复杂度分析、变体识别思路和一套自己的调试经验。保证你看完之后遇到滑动窗口题目能有一个稳定的分析路径而不是靠刷题数量硬堆。2. 滑动窗口的两种基本形态固定窗口与动态窗口2.1 固定窗口左边先走一步右边只能跟一步先聊最直观的固定窗口。所谓固定窗口就是窗口长度恒定不变。比如上面提到的“长度为K的子数组最大和”K就是定死的。实现上有一种非常符合直觉的写法先让右指针从0走到K-1算出一个初始窗口的和然后右指针继续往后走每走一步左指针也同步走一步保持窗口宽度永远是K。def max_sum_fixed(nums, k): n len(nums) if n k: return 0 current_sum sum(nums[:k]) max_sum current_sum # right 从 k 开始left 从 0 开始同步移动 for right in range(k, n): left right - k current_sum nums[right] # 新元素进窗口 current_sum - nums[left] # 最左侧元素出窗口 max_sum max(max_sum, current_sum) return max_sum这段代码有一个大家容易搞混的点left是谁left right - k。因为窗口长度固定为k当右指针到达right时窗口的左边界必然是right - k。所以固定窗口不需要显式维护left变量只需要在更新收益时把nums[right - k]减掉就行。固定窗口在工程里经常用来做时间序列的滚动统计比如最近7天销售额、最近30天活跃用户数。你不需要维护一个动态条件只要宽度不变代码写起来是最省心的。2.2 动态窗口右边扩、左边缩一切取决于条件动态窗口复杂了不少但也是面试和高频业务场景里出现最多的形态。它不再以“长度固定”为约束而是以“某个条件满足与否”来决定窗口如何变化。典型场景是求“和不超过S的最长子数组长度”。这时窗口长度不固定我们需要不断调整右边界去扩大窗口当窗口内元素之和超过S时就移动左边界收缩窗口直到满足条件再尝试继续扩大。def longest_subarray_sum_less_than_s(nums, s): n len(nums) left 0 current_sum 0 max_len 0 for right in range(n): current_sum nums[right] # 右指针扩张把新元素纳入窗口 while current_sum s: # 不满足条件收缩左侧 current_sum - nums[left] left 1 max_len max(max_len, right - left 1) return max_len看到这里你应该注意到动态窗口的一个核心特征left不一定每次移动一步它可能连续移动多次直到窗口重新变得“合法”。这个while循环就是动态窗口的灵魂所在。我早期犯过一个错误在收缩时只缩一次也就是用if而不是while。结果窗口仍然不满足条件但右指针已经继续前进了后面计算出的所有窗口长度全是错的。尤其是当窗口内数字较大的时候一次收缩根本不够。后来我总结出一条纪律只要条件是“不满足则收缩”并且收缩操作可能多次触发就一定用while。2.3 两种形态如何选择判断固定还是动态最关键的信号是约束条件。如果题目明说“长度恰好为K”“长度为L”那大概率是固定窗口。如果题目说“最多”“不超过”“至少”“包含”这类模糊限制条件那往往是动态窗口。你可以在读题时就把约束词圈出来它会告诉你该用哪种模板。还有一点需要提醒有些题目虽然看起来很动态但窗口长度实际是固定的。比如求字符串中所有“字母异位词”的起始位置目标词长度是确定的所以窗口长度也是确定的本质上还是固定窗口只是额外需要维护一个字符计数的状态。3. 从“可以跑”到“跑得快”复杂度分析与空间优化3.1 时间复杂度为什么是O(n)很多人对O(n)这个结论存疑原因在于动态窗口里既有for循环又有while循环怎么可能是线性的呢这是滑动窗口最容易搞混的一个点我用一个实际例子说明白。想象一下数组[1, 2, 3, 1, 2, 4]目标条件是子数组和不超过5。右指针从头走到尾这个过程中左指针可能不断右移。但注意left只会向右移动不会回头。在整个过程中right最多增加n次left最多也只会增加n次。所以真正的总操作次数是2n级别也就是O(n)。这有点像两个人跑步右指针是兔子左指针是乌龟乌龟虽然有时候连续跳好几步但累计下来它跑过的总距离不可能超过赛道的总长度。每个元素最多被右指针“加入”一次被左指针“移除”一次这种“每个元素至多进出各一次”的特性就是滑动窗口线性时间的本质原因。3.2 空间复杂度和哈希表的取舍滑动窗口本身如果只需要维护一个整数和、最大值空间复杂度就是O(1)。但如果题目要求窗口内元素不重复或者要求统计字符出现次数那就需要一个哈希表来记录状态空间复杂度上升到O(K)K是字符集大小或窗口大小。这里有个常见的优化思路用数组代替哈希表。当字符集范围有限且已知时比如只有小写字母直接用长度为26的数组下标就是字符编码相对值。这样做有两个好处一是数组的读写比哈希表快二是省去了哈希函数的开销。def length_of_longest_substring_no_repeat(s: str) - int: last_index [-1] * 128 # ASCII 可见字符128足够 left 0 max_len 0 for right, ch in enumerate(s): idx ord(ch) if last_index[idx] left: # 当前字符上一次出现的位置还在窗口内 left last_index[idx] 1 # 把左边界跳到重复字符之后 last_index[idx] right max_len max(max_len, right - left 1) return max_len这个“无重复字符的最长子串”问题用数组代替哈希表是一步很明显的性能提升。我在实际刷题中见过很多人用defaultdict再加remove操作逻辑没问题但代码复杂度上来了处理边界反而容易错。能用数组就别整哈希表除非字符集很大或者元素类型不确定。3.3 单调性为什么滑动窗口能这么做前面说的做法能成立背后还有一个前提随着右指针扩大窗口“满足条件”的可能性通常是单调的。窗口变大窗口的和变大窗口变小窗口的和变小。因为窗口内元素都是正数或负数固定方向变化这种单调性让我们可以放心收缩。但如果数组里有负数这个单调性就破了。和可能随着窗口变大反而变小。这时候滑动窗口模板直接套用会出错你需要考虑单调队列、前缀和配合二分等更复杂的结构。我的建议是遇到负数先停止套模板回到问题本身去分析确认是否真的可以用滑动窗口。4. 套模板前的关键一步如何用状态量描述窗口4.1 窗口里要维护什么这是我认为滑动窗口最核心的一点不要把注意力全放在指针移动上先想清楚窗口里要维护什么状态。常见的状态量有这么几类目标信息维护方式适合题型窗口元素之和一个整数进入加离开减长度、数量类问题窗口内元素种类数哈希表/数组计数水果成篮、最长子串窗口内最大值/最小值单调队列固定窗口最值问题窗口内是否有重复字符哈希表/数组记录最后出现位置无重复最长子串窗口内满足条件的元素个数计数变量配合条件目标计数类题目我举一个水果成篮的例子加以说明题目给一个数组代表每一棵树结的水果类型你只能拿两个篮子也就是最多同时保留两种水果问连续采摘的最长棵树。这道题需要的状态是“窗口内水果种类数”。你当然可以用一个字典记录每种水果出现次数但更漂亮的写法是维护一个计数器变量并用type_count动态更新def total_fruit(fruits): count defaultdict(int) left 0 ans 0 for right, fruit in enumerate(fruits): count[fruit] 1 while len(count) 2: left_fruit fruits[left] count[left_fruit] - 1 if count[left_fruit] 0: del count[left_fruit] left 1 ans max(ans, right - left 1) return ans这里用len(count)表示窗口内水果种类数其实就是一个动态维护的“状态量”。我没有单独用一个变量去跟踪种类数而是直接使用字典长度代码反而更清晰。等我需要更多条件时再考虑用独立计数器。4.2 为什么先写状态再写指针我个人的经验是指针移动只是外壳状态更新才是灵魂。很多题你有思路但写不对是因为一开始就在纠结left什么时候移动、right怎么走而忽略了状态的更新条件。正确顺序是先确定窗口的合法性是由什么决定的再决定用哪种数据结构维护它最后才是写两个指针的移动逻辑。这样下来不管题目怎么变你分析起来都有条不紊。比如“最小覆盖子串”这道经典题要求找出包含目标串T中所有字符的最短子串。这里的“合法性”就是窗口内目标字符的出现次数已满足需求。此时需要两个数组分别统计目标串各字符个数和窗口内各字符个数再用一个变量matched记录已满足条件的字符种类数。def min_window(s: str, t: str) - str: need [0] * 128 for ch in t: need[ord(ch)] 1 have [0] * 128 left 0 matched 0 required sum(1 for x in need if x 0) min_len float(inf) start 0 for right, ch in enumerate(s): idx ord(ch) have[idx] 1 if have[idx] need[idx]: matched 1 while matched required: if right - left 1 min_len: min_len right - left 1 start left left_ch s[left] left_idx ord(left_ch) if have[left_idx] need[left_idx]: matched - 1 have[left_idx] - 1 left 1 return s[start:start min_len] if min_len ! float(inf) else 这段代码的关键就在matched这个变量。它不直接记录“某种字符出现了多少次”而是记录“有多少种字符已经达标”。为什么要这么设计因为题目要求的是“包含所有字符”而不是“包含所有字符且每种恰好多少次”。用matched合并同类条件可以把多目标问题压缩成一个整数变量收缩判断变成matched required非常干净。4.3 状态量在收缩时的顺序问题在动态窗口中收缩阶段有一个特别容易踩的坑先更新状态还是先移动left我的习惯是“先结算再移除”。也就是在left移动之前检查离开窗口的那个字符是不是让某个计数不再满足要求如果是先把matched减掉然后再减少计数再移动left。如果换过来先移动left再判断那么s[left]指向的元素已经变了计算结果完全错误。这个错误在“最小覆盖子串”里几乎人人都会犯一次我印象太深了。那次我把have[left_idx]减1放在了matched判断前面结果matched经常少减导致滑动窗口收缩过头最后输出的子串不对。从那时起我给自己定了一个规矩移除元素前先判断这个元素是不是状态量中的关键分子然后再实际移除它。5. 固定窗口里的高阶技巧单调队列维护最大值固定窗口还有一个很常见的变体窗口内求最大值。典型题目是“滑动窗口最大值”。如果用常规思路每次遍历窗口里的K个元素找最大值时间复杂度O(n*K)大数据量下直接超时。这时候需要引入单调队列。所谓单调队列就是队列里的元素从队首到队尾保持单调递减。窗口滑动时新元素从队尾入队同时把队尾所有比它还小的元素统统弹出队首元素如果已经滑出窗口就出队。这样队首永远是当前窗口的最大值。from collections import deque def max_in_sliding_window(nums, k): dq deque() result [] for i in range(len(nums)): # 保证窗口区间合法性队首元素索引不能在窗口之前 if dq and dq[0] i - k 1: dq.popleft() # 维护单调递减队尾所有小于当前元素的值都不再有价值 while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) if i k - 1: result.append(nums[dq[0]]) return result这段代码的while循环是核心。为什么要弹出所有比当前元素小的因为你后面找最大值时只要当前元素还在窗口内那些比它小的旧元素永远不可能成为最大值。它们留在队列里只是浪费空间和比较时间。这其实是一种强力的剪枝把窗口内“没有潜力”的元素提前淘汰。我第一次写出来时觉得这个设计和滑动窗口的主体思路不太一样。滑动窗口的主体讲的是“复用上一次的计算”而单调队列更像是在维护一个候选集合。但两者并不冲突窗口结构负责约束区间单调队列负责高效地回答窗口内最值这个子问题。固定窗口最大值在股票K线最高价、传感器滑动峰值、日志时间窗口峰值等场景中都很实用理解这套结构遇到同类型问题能直接迁移思路。6. 识别变体题型滑动窗口的家族图谱滑动窗口的题目千变万化但只要抓住核心要素识别起来并不难。我根据自己的刷题经验把常见变体分成几类整理成一张“识别清单”。6.1 连续子数组/子串类这类题目的共同点是要求一个连续的区间满足某个约束求最长、最短、数量或和。典型代表有长度最小的子数组和≥target乘积小于K的子数组无重复字符的最长子串共同套路是用右指针扩张用条件判断窗口合法性不合法就移动左指针收缩在每次合法状态时更新答案。6.2 字符计数与包含关系类这一类是在滑动窗口上叠加字符频次统计。题目往往会要求子串“包含某些字符”“包含某些字符且数量不少于”等。代表题目最小覆盖子串字符串的所有字母异位词找到字符串中所有字母异位词这类题最关键的变量是matched或distance它标记“有多少个需求已经满足”。一旦用了这个变量收缩条件就变得极简单。6.3 哈希表窗口不重复约束类问题要求窗口内不能有重复元素比如“无重复字符的最长子串”。滑动窗口配上哈希表/数组记录每个元素最近出现的位置一旦发现当前字符的出现位置在当前窗口内就把左边界跳到上一次出现位置的下一个位置。这里的跳跃不是逐个收缩而是一次跳到位。这是它与普通动态窗口的重要区别。普通动态窗口left是逐步递增的但这种跳变式left移动可以节省大量时间。6.4 固定窗口查询最值类上面提到的滑动窗口最大值就是这一类。它的窗口长度固定但状态量是窗口最大值。需要用单调队列或者双端队列维护窗口的有序信息。我给读者的建议是刷题时不要只套模板先按“窗口是否定长”“状态量是什么”“收缩时如何更新状态量”三个维度给自己写注释。时间久了你就建立起条件反射了。6.5 滑动窗口与双指针的区别很多人把滑动窗口和双指针混为一谈。严格来说滑动窗口是双指针的一个子类型双指针还包含相向双指针比如有序数组两数之和也包含快慢指针比如链表找环。滑动窗口专指同向双指针两个指针都只向一个方向移动窗口描述的就是两个指针之间的区间。如果你听到题目说“双指针”先别急着套滑动窗口模板先确认两个指针是否同向移动。相向双指针和滑动窗口在代码结构上完全不同。7. 遇到边界和负数怎么办滑动窗口的失效边界滑动窗口虽然强但不是万能的。我在实际做题中总结了三种它容易失效的情形你需要注意。7.1 数组存在负数当子数组和可能出现负数时窗口长度增加不一定让和增加那么“当前窗口不满足条件就收缩”这个策略就失效了。因为扩大窗口有可能让和变小反而满足条件所以简单地右扩左缩无法覆盖所有可能。这种情况下要找“和不超过S的最大长度”就需要把每个前缀和求出来然后配合有序结构做二分时间复杂度上升到O(n log n)。不要试图用滑动窗口绕过去那会得到错误答案。7.2 需要所有区间而非最值如果题目要求“求所有满足条件的子数组”滑动窗口可以统计一些计数型问题比如“乘积小于K的子数组个数”。具体做法是当窗口满足条件时每新纳入一个右端点就贡献right - left 1个以right结尾且满足条件的子数组。但如果要求把所有子数组的具体内容全部列出来滑动窗口只能逐个输出复杂度就和输出数量成正比无法避免。此时不要期望模板解决一切老老实实考虑暴力套前缀或者分治。7.3 状态量难以在O(1)时间更新有些条件非常复杂比如窗口内元素某种组合的值满足某个条件。如果状态量更新本身需要O(窗口长度)时间那滑动窗口的线性优势就没了。解题前先评估这个状态量能否随left/right移动在常数时间内更新不能的话别硬套。8. 一套稳定好记的滑动窗口调试与书写流程8.1 书写模板不同人有不同的封装习惯我自己常用下面这个结构它适合绝大多数动态窗口问题left 0 state initial_state() answer initial_answer() for right in range(len(nums)): # 1. 扩大窗口把nums[right]纳入状态 update_state_with_add(nums[right]) # 2. 收缩窗口直到状态重新合法 while not valid(): remove_state(nums[left]) left 1 # 3. 更新答案注意窗口此时是合法窗口 answer update(answer, right - left 1) return answer这个结构的通用性在于它把“右指针扩张”“左指针收缩”“状态更新”三个阶段分得很清晰。新手写代码时容易把状态更新和指针移动混在一起结果出现顺序错误。哪怕多写几行我建议也保持这三段的逻辑独立性排错方便。8.2 常见bug自查清单每次写完我都会对照下面几个点自查一遍检查项正确做法常见错误收缩时用if还是while只要可能连续收缩就用while用if只缩一次移除元素前是否结算matched先判断再移除先移除再判断窗口合法时是否更新答案合法后再更新合法前更新指针是否越界检查元素是否存在访问了空窗口的left状态量是否处理重复元素left跳变时更新重复时只缩一步8.3 一个调试案例说一个具体问题我在写“长度最小的子数组”时因为没把ans初始值设成足够大导致最后返回了0。原因是当整个数组都不满足条件时ans一直没更新初始值0被返回了。正确做法是把ans初始化为inf或者用一个标志位表示是否找到过可行窗口。另外一个常见问题是窗口内元素全为正数时我可以把内层循环写成while sum_ target这没问题。但如果数组元素为正数和负数混合这种写法就完全错了。调试时先确认题目数据范围是否满足单调性再写代码能省很多时间。9. 从刷题到工程滑动窗口的真实应用场景9.1 流量控制与日志统计在网关系统里经常需要统计最近1秒、最近1分钟的请求数并据此做限流。这个“最近1秒”本质上就是一个时间窗口只不过时间窗口的边界需要处理乱序到达的数据。工程实现上可以用一个队列记录时间戳每来一个请求把当前时间戳加入队列尾部同时从队列头部弹出所有超过时间窗口的旧时间戳队列长度就是当前窗口内的请求数。这和滑动窗口的动态窗口收缩逻辑完全一致。9.2 股票与传感器数据实时计算连续K分钟内的最高成交价等价于固定窗口最大值问题。你会维护一个单调递减的双端队列把过期索引弹出把比当前价格低的旧索引弹出每次队首就是当前窗口最大值。这种写法比每次重新遍历K个数据高效得多。9.3 基因序列与文本分析在一段DNA序列中寻找所有长度为L且GC含量满足条件的片段或者在一篇长文中找到包含所有关键词的最短摘要都是滑动窗口的经典实际应用。前者是固定窗口加计数后者是动态窗口加哈希表和我在前面写的模板完全同构。从我的经验来看理解滑动窗口最好的方式不是多刷几百道题而是把每个问题的“窗口状态量是什么”“收缩条件是什么”“答案在什么时候更新”这三个问题回答清楚。只要这三点清晰代码写出来基本不会有大问题。我个人还有一个习惯每道滑动窗口题做完之后会用一句话总结它的本质比如“这题本质是固定长度窗口内维护字符频次”然后记录在错题本里。下次遇到新题先看能不能对号入座到已有的总结里能对上的话解题效率会直线上升。希望这篇文章能帮你把滑动窗口从“看着会写着错”变成“提笔就写写完就对”。
阅读完成 · 觉得有帮助？
