定长滑动窗口模板详解：从初始化到边界避坑

定长滑动窗口这个技巧说实话是双指针家族里最“没脾气”的一个——它不像快慢指针那样需要琢磨什么时候该动指针也不像动态规划那样需要想破脑袋设计状态转移。正因为如此很多人觉得它简单真正上手做题时却总是在边界条件上栽跟头要么窗口长度少算了一个要么循环终止条件写错要么干脆没意识到有些题必须刻意维护窗口长度而不是只靠指针移动。我看后台私信里不少读者提到基础篇1里讲过的“固定长度子数组最大平均值”这类题能看懂但换个题型比如统计定长窗口里的某种状态、按窗口切分字符串就又模糊了。这篇“基础篇2”就把定长滑动窗口这层窗户纸捅破不讲那些花哨的优化技巧只聚焦一件事在窗口长度恒定的前提下如何写出逻辑自洽、边界稳定、可以直接套用的代码。不管是刚接触双指针的初学者还是刷题有一定量但总被边界坑到的同学这篇都是为你准备的。1. 定长滑窗的本质从暴力解法的重复计算说起1.1 一个典型的不能再典型的问题固定长度子数组最大值假设给你一个整数数组要求所有长度为 k 的连续子数组中的最大值。这是定长滑动窗口最常见的入门题之一。很多人第一反应是暴力枚举外层循环遍历每个起点内层循环累加 k 个元素找出最大值。这个思路在数组只有几十个元素时没有任何问题但当数组长度达到十万、百万级别时间复杂度 O(n \times k) 带来的性能开销就已经不可接受了。让我们具体感受一下为什么会慢。数组长度为 n窗口长度是 k暴力法的计算次数是 (n - k 1) \times k。当 n100000、k50000 时这个数大约是 25 亿次操作——即使每次操作只需要一条简单的比较指令在现代 CPU 上也需要几秒钟才能跑完。这不是靠编译器优化能救回来的。暴力法慢在哪儿慢在它把每个窗口看作完全独立的任务。可实际上窗口从位置 i 滑到位置 i1 时有 k-1 个元素是重复出现的。暴力法对这些重复元素做了完全一样的比较和累加浪费了大量算力。定长滑动窗口的核心思路就是把窗口的滑动看作一次“有记忆”的更新而不是每次都从零开始。1.2 滑动窗口的视角转换增量计算滑动窗口的做法是先算出第一个窗口的结果然后开始滑动。每次滑动时窗口“吐出”最左边的一个元素同时“吞入”右边的新元素。也就是说我们不再重新计算整个窗口而是在上一个窗口的基础上做一次局部更新。这里的关键在于这个更新操作的复杂度。如果更新操作是 O(1) 的那么整个算法就是 O(n) 的不管窗口长度 k 有多大性能都稳定。这就是定长滑动窗口天然的优势所在——它的时间复杂度只和数组长度 n 有关和窗口长度 k 彻底解耦。以“固定长度子数组最大平均值”为例当窗口滑动时新的窗口和等于旧窗口和减去离开的元素再加上新进入的元素。这个操作是 O(1) 的所以整体复杂度从 O(n \times k) 降到了 O(n)。当 k 很大时这种差距是碾压性的。理解这个增量计算的思想比背任何模板都重要——因为几乎所有定长滑动窗口的题目都是在“增量更新窗口内维护的某个状态值”。1.3 为什么说“定长”是滑动窗口里最特殊的一类在正式进入代码之前我们必须先把“定长”和“变长”区分开。定长滑动窗口字面意思就是窗口长度固定为 k从头滑到尾。变长滑动窗口则不同窗口的左右边界可能根据条件动态调整窗口长度不固定典型代表是“无重复字符的最长子串”“长度最小的子数组”。定长窗口之所以特殊是因为它的左右指针移动节奏是固定的——每轮循环右指针前进一位左指针跟着前进一位窗口就像一个固定长度的列车车厢在数组轨道上匀速前进。这种匀速感让循环结构变得极其清晰一个循环搞定全部操作不需要像变长窗口那样嵌套 while 来调整左边界。但定长窗口也因为这层“简单”的外表让很多人忽略了边界细节。一个常见的错误是把窗口的维护逻辑放在循环体里任意位置导致某次滑动时窗口计数错乱。后面我会专门讲这个。现在先建立一个共识定长滑动窗口的代码框架应该是“先初始化窗口再滑动窗口”这两步缺一不可、顺序不可颠倒。2. 一套足够稳的模板写法初始化在前滑动在后2.1 模板代码逐行拆解直接给出一套我认为最稳妥的定长滑动窗口模板用 Python 写语言无关理解思路后搬到 C、Java、Go 都很容易def fixed_window(nums, k): n len(nums) if n k: return None # 窗口长度大于数组长度无解 # 阶段一初始化第一个窗口 window_sum 0 for i in range(k): window_sum nums[i] # 记录初始窗口的结果 result window_sum # 阶段二滑动窗口 for i in range(k, n): # 先移出左边界元素再加入右边界新元素 window_sum nums[i] # 新元素从右侧进入 window_sum - nums[i - k] # 离窗口的元素从左侧离开 # 更新结果 result max(result, window_sum) return result这个模板的形态非常固定甚至可以说有点机械。但机械不等于死板恰恰是这种固定结构能最大限度减少边界错误。2.2 为什么要单独初始化第一个窗口而不是在循环里统一处理你可能会有疑问为什么不把初始化也塞进滑动循环里比如让左指针从 0 开始右指针从 k 开始第一轮就处理窗口 [0, k-1]这种想法的痛点是滑动循环的每一轮都是“基于上一轮窗口的结果做增量更新”而第一轮上轮并不存在巧妇难为无米之炊。更关键的是初始化第一个窗口可以帮我们确定一个有效基准。很多结果不是简单累加和可能是一个复杂的状态比如哈希表里的字符计数、某个数据结构里的数值。如果先在循环外把基准建好后续每轮都基于一个合法状态做 O(1) 更新逻辑就会非常顺畅。一旦试图把初始化并入循环就不可避免引入 if 分支判断“当前是不是第一轮”这不仅让代码变难看还增加了心智负担和出错概率。所以在实际编码时我强烈建议你严格执行“先初始化再滑动”的两阶段结构。哪怕你已经有多年刷题经验这个习惯也能帮你节省大量调试时间。2.3 先加入还是先移除滑动顺序的黄金法则窗口从 [i-k, i-1] 滑到 [i-k1, i] 时先移动谁再看模板里我写的顺序先加右侧新元素再减左侧离开元素。这里其实有一点讲究。如果先减后加会短暂出现窗口长度不足 k 的中间状态。对于只计算累计和的场景先减后加没任何问题。但假设你维护的是一个需要精确反映窗口内容的哈希表中间状态可能让代码在“某个时刻”读到不完整的窗口状态——比如你在中间插入了调试输出或者更糟的是你借助了某个回调用函数读窗口状态。更稳妥的做法是维护“窗口内容始终完整”这个不变量。先加右侧元素窗口长度短暂变成 k1多了一个右侧元素然后减掉左侧元素窗口长度恢复 k。这个过程中只有长度 k1 的那一步是瞬时的但它从未出现过长度不足 k 的情况。如果窗口内容的状态一致性有要求这个顺序更安全。当然如果你纯算累计和先加先减无所谓结果一模一样。但从养成“肌肉记忆”的角度我建议统一采用“先加后减”因为往后遇到的题大概率是哈希表、双端队列这种对状态敏感的容器结构。2.4 边界条件的三个经典坑用这套模板写代码仍然有三个边界坑值得一提每一个我都亲身踩过坑一忘记判断 n k。如果数组长度小于窗口长度初始化阶段就会访问越界。很多人写数组题默认输入一定合法但实际工程或面试中这种异常输入必须提前拦掉。坑二循环的起始位置写错。很多初学者把滑动循环写成for i in range(k1, n)导致第一个被跳过的 i k 对应的滑动操作没执行结果缺失了窗口 [1, k] 的答案。我建议你在循环里打印每一轮的窗口区间来验证当 i k 时窗口区间应该是 [1, k]对应的代码是加入 nums[k]、移出 nums[0]。坑三结果初始化值选错。如果求最大值result初始化成 0 可能不够——因为窗口和可能全是负数。稳妥的做法是直接初始化为第一个窗口的结果然后在滑动循环里逐步比较更新。这一点与“先初始化窗口”的思路一脉相承第一个窗口已经是一个合法解直接用它作为基准即可。3. 从模板到实战三个经典问题的完整推理3.1 定长窗口最大值叠加单调队列的进阶前奏前面模板讲的是“固定长度子数组最大平均值”那是定长窗口里最基础的应用。现在来看一个稍进阶的问题求每个定长窗口内的最大值。如果你直接用 O(n \times k) 的办法在每个窗口内扫一遍找最大值理论上没错但完全没有利用滑动窗口的增量特性。这实际上是“滑动窗口最大值”这道经典题但如果我们只考虑定长基础最简单的实现可以先用一个有序容器维护窗口内元素每次滑动时删除离开元素、插入新元素然后取容器最大值。但这样复杂度是 O(n \log k)不是最优解。最优解法是用单调队列双端队列维护窗口内元素的下标保证队列中元素严格递减。当窗口滑动时新元素入队前先把队尾所有小于等于它的元素弹出同时把已经滑出窗口的队头元素弹出。这样队列头部始终是当前窗口的最大值。因为每个元素最多入队出队各一次整体复杂度 O(n)。这个题放在“基础篇2”里讲是合适的因为它虽然引入了单调队列但整体思路仍然是定长滑动窗口的增量更新逻辑每滑一次队列做一次出队入队仅此而已。后面我会细说单调队列的边界问题这里你先意识到一点即使换成了更复杂的数据结构窗口滑动的主干逻辑依然没变变的只是状态更新的方式。3.2 定长窗口的字符统计与哈希匹配不是只有数组才能滑当窗口里的元素不是数字而是字符时套路依然成立但状态维护需要从“数值累加”切换成“频率统计”。典型的例子是 LeetCode 上的“存在重复元素 II”——判断数组中是否存在两个不同下标 i 和 j使得两个下标之差的绝对值不超过 k并且两个位置上的值相等。这个问题表面上是哈希查找但换个角度看就是定长滑动窗口长度为 k1内的重复元素检测。维护一个哈希集合滑动窗口时把左侧离开的元素移出集合把右侧新元素加入集合如果新元素已经在集合中说明窗口内存在重复值直接返回 true。字符统计类的题也是如此比如“定长窗口内元音字母的最大个数”。第一步先统计第一个窗口中元音字母的数量之后每滑动一次检查移出的元素是不是元音、新加入的元素是不是元音相应更新计数。所有操作都是 O(1) 的整体还是 O(n)。这类题看起来和数值类不同但骨架完全一致——只是窗口状态的定义从“和”变成了“频率计数”。3.3 构建定长窗口的通用思维状态是灵魂在这个小节我想把前几个例子里隐藏的通用规律抽出来。定长滑动窗口本质上是个“运动的状态容器”——窗口长度是容器大小状态是这个容器内所有元素共同维护的某种信息滑动是容器整体右移的操作。至于状态具体是什么完全由题目决定求最大平均值状态是窗口内数值总和。求元音字母个数状态是窗口内元音字母计数。判断是否有重复状态是窗口内元素集合。求窗口最大值状态是窗口内单调递减队列。同一个滑动框架只要替换状态维护逻辑就能解决一大类问题。这就是我反复强调“先把结构写稳”的原因——当你的代码骨架足够稳定剩下的工作就是往骨架里填不同的状态更新逻辑。面对一道新题你应该问自己三个问题窗口长度是多少窗口内维护什么状态滑动的每一步如何增量更新这个状态三个问题想清楚代码自然就出来了。4. 边界条件与易错点排查我的真实踩坑记录4.1 左闭右开 vs 左闭右闭从根源上避免索引错乱定长滑动窗口的边界问题归根到底来源于一个选择你用左闭右开区间还是左闭右闭区间来描述窗口。比如窗口长度为 k用左闭右闭区间表示是 [left, right]其中 right - left 1 k用左闭右开区间表示是 [left, right)其中 right - left k。两者没有绝对的优劣但你必须全篇统一。很多人出问题恰恰是因为一个程序里混用了两种区间表示初始化时用闭区间滑动时却又按开区间计算下标导致一两个元素的偏差整个结果全部错误。我的经验是始终使用左闭右闭区间 [left, right]。理由是这个区间定义符合直觉而且检查窗口是否合法时只需要看right - left 1 k不需要额外转换。以滑动循环为例初始窗口是 [0, k-1]第一次滑动后窗口是 [1, k]代码中用i表示右边界时左边界是i - k 1。这个公式不会错。4.2 初始化窗口时的越界与空窗口防护数组长度不够 k这属于输入不合法。但还有一种更隐蔽的情况是数组长度恰好等于 k。这是合法输入但滑动循环一次都不会执行程序会直接返回初始窗口的结果。如果你没意识到这一点可能会在测试用例上感觉“程序好像没跑”而莫名其妙。处理方式就是在初始化前检查 n k 然后尽早返回。除此之外另一种情况是 k 甚至可能为 0 或负数。虽然正常题目不会这么设计但在工程实践中参数合法性检查一定要做全面避免不必要的空指针和越界。4.3 变量命名与作用域导致的隐蔽 bug调试多了你会发现很多 bug 不是因为思路错而是因为变量名太像导致误用。比如window_sum和window_start写快了很容易把其中一个敲成另一个。更危险的是循环变量i复用——如果你在外层已经用了i内层又用了i某些语言里会出现变量遮蔽shadowing问题。我的习惯是给滑动窗口相关变量起名时带有明确语义left、right或window_start、window_end维护状态的容器叫state最终结果叫best或res。命名清晰不能直接消灭 bug但能显著降低 bug 出现的概率尤其在代码评审和后续维护时收益巨大。4.4 在 O(n) 时间内检查窗口状态别用 O(k) 的辅助操作这是我在指导别人时发现的高频问题。比如你维护的是一个窗口内元素的“频率哈希表”每次滑动后为了求当前窗口的某个值直接在循环内遍历哈希表的全部键计算——这是典型的 O(k) 操作会让整体时间复杂度退化为 O(n \times k)和暴力法没有任何区别。正确做法是在状态更新过程中同步维护一个额外的变量。例如“定长窗口内不同字符的个数”这类题不能在每次查询时重新统计哈希表大小而要在加入/移出元素时动态维护distinct计数如果某个字符从 0 变 1distinct 加一从 1 变 0distinct 减一。这样查询是 O(1) 的。这是定长滑动窗口性能优化的核心心法任何状态都必须走在更新的路上而不是在查询时才从头计算。5. 从定长到变长建立滑动窗口的体系化认知5.1 定长与变长的本质区别在哪里把定长和变长放在一起比较能更好地理解两者的适用场景。定长窗口解决的是“窗口长度固定求所有窗口内的某个指标”的问题左指针和右指针移动是同步的每轮各走一步。变长窗口解决的是“窗口长度不固定求满足某种条件的最短/最长窗口”的问题右指针持续扩张直到条件满足后收缩左指针寻找更优解。这两种模式在代码结构上差异明显。定长窗口是单层循环变长窗口往往是外层循环扩展右边界内层循环收缩左边界。容易混淆的是“最长无重复子串”这类题——它的窗口长度显然不固定但有人会误以为可以用一个固定窗口加 set 来维护。这个思路错在窗口长度本应随无重复性质而动态变化强行定长必然漏解。记住一个判断标准如果题目里所有窗口的长度都是同一个 k那就是定长如果窗口长度随条件变化那就是变长。这个标准看起来很朴素但真的能帮你快速分类题型。5.2 如何识别“伪定长”与“真定长”有一些题目表面没说窗口长度固定但仔细分析后会发现其实可以转化为定长问题。比如“长度为 k 的连续子数组的最大平均数”就是典型的真定长而“乘积小于 K 的子数组个数”从字面看窗口长度不定但它依赖的是“右边界固定时找出最长可行窗口然后窗口内所有以右边界结尾的子数组都可行”这个性质其实是变长窗口解法。我在刷题时养成了一个习惯拿到题先看能不能定义一个固定长度的窗口再看这个固定窗口是否能覆盖题目所有可能性。如果答案是肯定的优先使用定长窗口因为它逻辑简单代码也不容易出错。5.3 “基础篇2”之后该往哪走定长滑动窗口之上还有三条明显的进阶路径。第一条路径是数据结构升级比如用单调队列解决滑动窗口最大值用双端哈希表解决更复杂的计数问题。第二条路径是多窗口组合比如同时维护两个定长窗口并比较它们的状态。第三条路径是与二分答案结合比如“使所有子数组的和小于等于一个阈值所需的最小窗口长度”这类问题往往需要二分答案定长窗口验证。但所有这些进阶路径都需要你对基础模板有肌肉记忆般的熟练度。“基础篇2”的内容如果你已经吃透接下来可以开始刷 LeetCode 上标签为“Sliding Window”的中等难度题刻意练习把每个问题转化为“初始化窗口滑动更新”的框架。6. 关于这套思路我掏心窝的四个建议建议一手写模板十遍比看十篇博客有用。你可以用 3 分钟把模板背下来但距离真正掌握至少还需要独立手写十遍。每次不要抄凭记忆写。写错的地方就是你理解薄弱的地方值得停下来想一想为什么会错。建议二做题时故意在边界测试用例上反复确认。“数组长度为 1k1”“数组全负数求最大值”“窗口长度等于数组长度”这三种用例几乎能覆盖 90% 的边界 bug。每套完一个模板先跑这三个用例通过了再提交。建议三遇到新题先用小规模暴力解验证思路。如果你对某个问题的数学建模没把握可以先用 O(n \times k) 的暴力解把正确结果算出来然后用滑动窗口代码对比输出。这种对拍方式能帮你快速定位是思路错了还是实现错了。建议四把每道题的窗口状态更新逻辑单独抽出来写成注释。比如“# 加入 nums[right]更新 sum移出 nums[left]更新 sum”。这样既方便写代码的时候不迷路也能在回看代码时快速唤起记忆。定长滑动窗口从来不是一道难题它是一个基础工具。工具用得顺手的人未必比别人聪明只是他摸清了工具的脾气知道它在什么时候该做什么动作。你把这篇文章里的模板和边界细节消化掉再见到任何定长窗口相关的题就有底气说一句这题我能稳稳地写对。