滑动窗口这套算法我前阵子专门写了第一篇基础篇结果后台收到不少留言有人说模板背熟了但一换题就不会用有人说无重复字符最长子串自己做能过遇到最小覆盖子串就完全不知道从哪收窗口。这些问题其实都指向同一个卡点——滑动窗口的“变体”和“收缩时机”没吃透。这篇《优选算法——滑动窗口2》就把这些补上从什么时候该用滑动窗口、两类窗口的根本区别到三套高频模板、四道必刷题的手把手拆解再延伸讲滑动窗口在大数据处理、信号滤波甚至Verilog硬件实现里的工程玩法。无论你是准备面试、刷题入门还是做嵌入式或算法工程师这篇都能让你对“窗口怎么开、怎么滑、怎么停”有更完整的理解。滑动窗口看着简单——无非left和right两个指针。但把它用对需要的不只是模板而是对问题结构的判断力。我见过太多人栽在不该用滑动窗口的题上硬套或者在收缩窗口时少写一个循环导致结果错得离谱。下面我用实际做题的经验把这些坑一个一个趟给你看。1. 滑动窗口什么时候进场识别四类必考题1.1 连续区间问题的“探照灯”思维滑动窗口解决的核心问题有一个共同特征研究对象是连续的一段不是离散的多个点。连续子数组、连续子串这是第一道筛选条件。比如“和为K的子数组有多少个”显然不是滑动窗口的标准场景因为区间不满足单调性时窗口没法决定收缩方向。但“和大于等于K的最短子数组”就是典型滑动窗口——窗口越长和越大存在明确的单调变化方向。我常说滑动窗口像一把探照灯灯管长度代表窗口大小光照范围就是当前区间。你要找的是某个光照范围内是否满足目标条件。这个比喻有两点提醒第一探照灯不会跳着移动它从数组开头一路扫到结尾不会回头第二灯管长度随时可以伸缩这取决于你想探测的目标。把这两点记住很多变形题都能往这个框架上靠。第二个筛选条件是“最值问题”。最长、最短、最大、最小当题目问的是这种最值而且答案来自某个连续区间滑动窗口是优先级最高的候选方案。反过来如果题目问的是“是否存在某个排列”、“能否分割成几段”那大概率不是滑动窗口能直接解决的。1.2 两类窗口的本质区别稳定性窗口与可变窗口滑动窗口根据窗口长度是否固定分成两大类它们的代码模板大不相同。固定窗口长度恒定比如“大小为k的子数组的最大平均值”窗口从头滑到尾left和right同步移动代码结构是单层循环里left和right一起加一。可变窗口则要在循环里动态调整窗口先扩大后收缩典型如“无重复字符的最长子串”。判断方法很简单看条件是和窗口长度相关还是和窗口内容相关。固定窗口几乎都是“窗口大小k”直接出现在题目里可变窗口则依赖计数、求和、去重等状态变化。如果题目里出现了“最多k个”、“至少包含”这类模糊数量基本可以断定是可变窗口。固定窗口和可变窗口的适用场景我整理成下表方便做题时对照题目特征窗口类型例子窗口变化规律明确给窗口大小k固定窗口大小为k的子数组最大平均值left和right同步前进求最大窗口/最长子串可变窗口窗口内合法时扩张无重复字符的最长子串先扩右不合法就缩左求最小窗口/最短子串可变窗口窗口内合法时收缩长度最小的子数组、最小覆盖子串先扩右合法就缩左窗口内最值统计固定窗口单调队列滑动窗口最大值窗口滑动时维护队列这个表是做题时的第一层思维框架。看到题目先对号入座再决定套哪套代码比你硬背十个模板好用得多。1.3 滑动窗口的时间复杂度为什么是O(n)很多初学者想不明白为什么里面还有个while循环整体却是O(n)而不是O(n²)。关键在于每个元素最多被left访问一次、被right访问一次。right负责加入元素left负责移除元素它们都只往一个方向走永远不回退。所以总的操作次数不超过2n常数级别的线性复杂度。这个结论有严格保证吗有的。整体循环里虽然嵌套了while但这个while移动的是left指针而left在整个算法生命周期里最多移动n次。right指针同样最多移动n次。两个指针移动次数加起来是2n和n是线性关系所以总复杂度就是O(n)。这个理解很重要因为面试官问复杂度时你要是只说“看着像O(n)”会显得不踏实能讲出指针不回溯这个本质才让人信服。2. 先吃透两个核心问题哈希计数和收缩时机2.1 窗口状态维护哈希表/数组计数是不可或缺的窗口里装的是元素但我们要跟踪的往往是“窗口里每种元素出现了几次”。这就要维护一个频率计数结构。多数语言里用哈希表C语言则优先用数组——如果字符集有限比如英文字母只有26个或ASCII码256个直接用数组下标映射字符访问O(1)性能远好于哈希表。我习惯把这种计数结构叫“窗口状态”它和窗口本身一样重要。窗口状态必须支持三种操作加入元素时计数加一移除元素时计数减一查询某个元素或所有元素当前是否满足条件。这三个操作设计得顺不顺直接决定代码的简洁程度。很多题目卡住不是窗口逻辑难而是计数结构没选对导致查询条件时还得遍历一次窗口。比如无重复字符问题是看当前元素计数是否大于1用数组查一下O(1)就解决了。但最小覆盖子串要判断“窗口是否包含了所有需要的字符”如果每次判断都遍历整个哈希表总复杂度就会退化到O(n×字符集大小)。正确的做法是用额外变量统计匹配数这在后面代码里会细讲。2.2 收缩窗口的判断合法状态和非法状态怎么区分可变窗口最容易出错的地方在于什么时候收缩答案取决于你对“合法窗口”的定义。我们用一个布尔条件来表示窗口是否满足题目要求。对于求最长子串的题窗口始终保持合法一旦加入新元素导致不合法立即收缩到重新合法。对于求最短子数组的题窗口在多数情况下不合法一旦满足条件就要收缩并且边收缩边记录答案。核心口诀我总结为八个字求长则保求短则收。求最长我们要保持窗口一直合法不合法了才左移左移到重新合法为止求最短我们要在窗口合法时尽量收窄一旦不合法就停止收缩转去扩展右边界。这个方向如果搞反代码一定会出逻辑错误。另外一个高频错误是收缩时漏掉循环。很多新手写if而不是while结果窗口没有收缩到目标状态答案自然不对。收缩不是一步到位的可能左移一次后条件仍然满足求短场景或者仍然不满足求长场景所以必须用while持续收缩直到状态发生反转。2.3 模板代码C语言版万能滑动窗口骨架直接给一套我常用的C语言模板覆盖九成可变窗口题。它把窗口状态和收缩逻辑都放在明面上调试也方便。// 通用可变窗口模板 // arr: 输入数组/字符串 // n: 数组长度 // windows: 函数指针判断当前窗口是否满足题目要求 // add(x): 把元素x加入窗口 remove(x): 把元素x移出窗口 // 以最短满足条件的窗口为例 int shortestWindow(int* arr, int n) { int left 0, ans INT_MAX; // 初始化窗口状态 for (int right 0; right n; right) { // 1. 加入arr[right]到窗口 add(arr[right]); // 2. 窗口满足条件时收缩 while (windowIsValid()) { // 3. 更新答案 if (right - left 1 ans) ans right - left 1; // 4. 移除arr[left]left右移 remove(arr[left]); left; } } return ans INT_MAX ? -1 : ans; }这套模板的核心在while循环。每次右指针扩展后检查是否满足条件一旦满足就不断收缩记录下所有可能的答案直到条件被破坏。注意答案更新要放在移除元素之前因为此时窗口刚好满足条件且是本次循环里的“最小可能窗口”。如果放在移除之后下次while条件可能已经不满足答案就漏了。求最长窗口时把条件判断反过来在窗口不合法时收缩答案更新放在退出while之后。模板只能解决共性部分每道题的差异性主要在add、remove和windowIsValid这三个函数上。把这三个函数设计好题目就解了一半。下面用四道经典题来演示怎么填充这套模板。3. 四道必刷题实操从思路到C语言代码完整记录3.1 无重复字符的最长子串计数数组加双指针题目很经典给一个字符串找出其中不含有重复字符的最长子串的长度。看到“最长子串”和“不重复”第一反应就是可变窗口加频率计数。窗口合法性条件定义为窗口内所有字符计数都小于等于1。每次右指针加入新字符如果该字符计数变成2说明窗口非法就移动左指针移除左侧字符直到该字符计数恢复为1。C语言实现我直接用256大小的数组作为计数器。字符可以转成无符号整数索引比用哈希表省去计算哈希和碰撞处理的开销。核心代码如下int lengthOfLongestSubstring(char* s) { int freq[256] {0}; int left 0, ans 0; int n strlen(s); for (int right 0; right n; right) { unsigned char c s[right]; freq[c]; while (freq[c] 1) { // 窗口非法收缩 unsigned char lc s[left]; freq[lc]--; left; } // 此时窗口合法 if (right - left 1 ans) ans right - left 1; } return ans; }代码里最有意思的是while条件直接用freq[c] 1判断不需要检查整个窗口的每个字符。因为新加入的字符是唯一可能破坏合法性的元素其他字符之前都满足计数不大于1。这个细节很多人没意识到以为每次都要遍历窗口检查所有字符那就把O(n)写成了O(n²)。举个例子走一遍s abcabcbb。right到2时窗口是abc长度3ans更新为3。right到3加入afreq[a]变2进入while移除s[left]即afreq[a]变1left到1。退出时窗口是bca长度还是3。right到4加入b触发收缩移除bleft到2窗口变cab。整个过程left和right都单向移动每步操作O(1)总复杂度O(n)。我刷题时习惯手推这种小样例每一步都标注freq和left位置对理解代码帮助很大。3.2 长度最小的子数组最短窗口的收缩节奏题目给定一个正整数数组和一个目标值target找和大于等于target的最短连续子数组。如果不存在返回0。这题的条件是“和大于等于target”属于求最短窗口套模板时注意窗口合法条件是sum target合法时收缩并更新答案。数组元素是正数所以right加入元素后sum单调递增left移除元素后sum单调递减满足滑动窗口的单调性前提。int minSubArrayLen(int target, int* nums, int numsSize) { int left 0, sum 0, ans numsSize 1; for (int right 0; right numsSize; right) { sum nums[right]; while (sum target) { if (right - left 1 ans) ans right - left 1; sum - nums[left]; left; } } return ans numsSize 1 ? 0 : ans; }注意收缩时不能停下来因为收缩后窗口可能仍然满足sum target比如target是8窗口是[3, 5, 2]sum10移除3后sum7刚好不满足了但如果窗口是[3, 5, 2, 4]sum14移除3后sum11仍满足必须继续收缩到[2, 4]才退出。while循环就是用在这里的漏掉一次收缩就可能多算长度。我见过有同学觉得这题“不是滑动窗口”因为窗口里数字加起来不就是个和吗但关键点在“连续子数组”和“正数数组”这两个前提缺一不可。如果数组含负数窗口长度增加时sum不一定增加右指针就不能保证单调扩展那就得回到前缀和加二分或哈希解法。这也是滑动窗口的适用边界必须有单调性。做题前先确认数据特性比直接套模板重要得多。3.3 最小覆盖子串用count变量代替哈希表遍历这题是滑动窗口里最有分量的一道也最考验状态维护的设计。给两个字符串s和t在s里找包含t所有字符的最短子串。注意“包含所有字符”包含重复字符比如t是AABC则子串里至少要有两个A、一个B、一个C。维护两个频次数组need统计t的每个字符需求window统计当前窗口的每个字符数量。再用一个变量count表示当前窗口有多少个字符已经达到需求数量count t的字符种数时窗口合法。为什么要多设计一个count如果不加count每次判断窗口是否合法都要遍历整个need数组复杂度会乘上字符集大小。用count变量把“是否合法”的判断降到O(1)这是滑动窗口优化的经典技巧。char* minWindow(char* s, char* t) { int need[128] {0}, window[128] {0}; int tlen strlen(t), slen strlen(s); int needCnt 0; // t中不同字符的个数 for (int i 0; i tlen; i) { int c t[i]; if (need[c] 0) needCnt; need[c]; } int left 0, count 0, ansLeft -1, ansLen slen 1; for (int right 0; right slen; right) { int c s[right]; window[c]; // 如果当前字符的窗口数量刚好达到需求count加一 if (window[c] need[c]) count; // 窗口合法时收缩 while (count needCnt) { if (right - left 1 ansLen) { ansLen right - left 1; ansLeft left; } int lc s[left]; if (window[lc] need[lc]) count--; // 移除会破坏合法性的字符 window[lc]--; left; } } // 根据ansLeft裁出子串返回省略返回细节 if (ansLeft -1) return ; char* result (char*)malloc(ansLen 1); strncpy(result, s ansLeft, ansLen); result[ansLen] \0; return result; }注意窗口收缩时count的更新逻辑只有移除的字符在移除前恰好满足需求window[lc] need[lc]移除后才会不满足count减一。如果移除前已经超量window[lc] need[lc]移除后仍满足需求count不变。这个判断非常容易写错我第一版就漏了这个条件导致ec、aab这类重复字符多的用例全错。还有个小细节当window[c]从0加到恰好等于need[c]时count加一而不是window[c] need[c]时。因为超过需求后窗口是否合法不影响count已经计过这个字符了。多计会出错。这一点是count技巧的精髓建议在纸上推演十行用例胜过背十遍代码。3.4 滑动窗口最大值固定窗口和单调队列的搭配如果题目说“给一个整数数组和窗口大小k每次滑动一个位置求每个窗口的最大值”这题和前面不太一样——窗口长度固定但要求输出窗口内的最大值而且窗口每滑动一次就要输出。暴力方法是每次扫描窗口内k个数复杂度O(nk)k大时直接超时。正确解法是单调队列双端队列里存的是下标且按数值从大到小排列队头永远是当前窗口最大值。#define MAXN 100005 int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) { int* result (int*)malloc((numsSize - k 1) * sizeof(int)); int q[MAXN], head 0, tail 0; // 手动双端队列存下标 *returnSize numsSize - k 1; int idx 0; for (int i 0; i numsSize; i) { // 移除超出窗口范围的过期下标 while (head tail q[head] i - k) head; // 维护单调递减队列新元素大于队尾队尾出队 while (head tail nums[q[tail - 1]] nums[i]) tail--; q[tail] i; // 窗口满k时记录答案 if (i k - 1) { result[idx] nums[q[head]]; } } return result; }这个解法的精妙之处在于队列里存的不是窗口全部元素只保留“有可能成为最大值”的元素。一个元素如果比它右边的另一个元素小那么在它俩都还在窗口里的时候它永远当不了最大值直接淘汰。这样每个元素最多入队出队一次整体复杂度还是O(n)。我在一开始想用优先队列或二叉堆做后面发现单调队列更简洁不需要删除特定元素这种堆的麻烦操作。值得留心的是队列维护的是下标不是值。存下标的好处是可以通过下标判断元素是否已经滑出窗口。存储值的话每次滑动还要在队列里搜索下标超范围的值复杂度就乱了。这道题是固定窗口与单调队列组合的典型面试里经常作为考察重点值得单独刷两遍。4. 从在线算法到工程设计滑动窗口在滤波和硬件里的玩法4.1 滑动窗口滤波模型数据平均化与异常值抑制滑动窗口不只是做算法题它在信号处理里有个特别常见的应用滑动窗口滤波也叫移动平均滤波。它的思想非常简单——维护一个固定长度N的窗口每来一个新数据就计算窗口内N个数据的平均值作为当前输出窗口整体往后滑一格。这个操作本质上是低通滤波把高频噪声平均掉适合平滑传感器数据、行情曲线、加速度计读数等。举个例子用MPU6050读加速度数据原始数据往往带高频抖动。如果每次读数直接拿去算角度显示会晃得厉害。用滑动窗口取平均值比如窗口大小5连续采集5个值再平均曲线立刻平稳很多。代价是延迟增加——输出不能立刻反映最新值平均本身就引入了滞后。窗口越大越平滑但延迟也越大。这就是滤波参数选择的根本矛盾。实际工程里窗口大小N怎么定要看信号的频率和噪声的特性经验法则是窗口宽度大致覆盖一个半信号周期能较好平滑又不过度失真。4.2 滤波延迟的计算和窗口宽度的平衡很多人在嵌入式里做滑动窗口滤波大概知道要开个数组存数据但不知道延迟怎么量化。假设窗口宽度为N我们输出的是当前窗口的算术平均值。如果把窗口看成对数据流做卷积卷积核是N个1/N的矩形脉冲那么它的群延迟是(N-1)/2个采样周期。换句话说输出波形会比原始波形滞后大约半个窗口宽度的采样时间。实时性要求高的系统比如PID控制回路延迟太大可能导致相位裕度下降、系统震荡。这时候滑动窗口滤波就不一定适合了可以考虑指数加权移动平均它的延迟更小。反过来离线处理数据不在乎延迟只在乎平滑度窗口可以开大一点。我用滑动窗口滤波处理IMU数据时N10的延迟是5个采样周期按照100Hz采样就是50ms如果控制系统响应带宽是10Hz这个延迟就有明显影响需要折中。这个账建议每个做信号处理的同学都亲自算一遍。4.3 Verilog实现滑动窗口移位寄存器替代内存数组滑动窗口在软件里用数组加指针很容易但在硬件里如果数据是流式输入的用一个RAM加地址指针当然也行但更自然而高效的做法是移位寄存器。每来一个时钟沿新数据从最右端移入原来最左端的数据被移出丢弃窗口内容就自动更新了。窗口里所有数据都能被组合逻辑或寄存器即时读取不需要手动维护地址。一个窗口宽度N4的Verilog滑动窗口均值滤波器大致结构是四级寄存器链串联每级寄存器存一个采样值。每来一个有效时钟data_in赋值给reg3reg3赋给reg2reg2赋给reg1reg1赋给reg0。求平均值就是把reg0到reg3加起来除以4除以4在硬件里就是右移两位完全不用除法器。这就是硬件里为什么常用滑动窗口均值滤波——计算代价极小流水线清晰而且没有乘法器负担。如果只想做“最近N个值的布尔判断”比如检测连续N个时钟周期都有某个信号那移位寄存器更简单把N位寄存器右移一位输入接到最高位然后检查寄存器里是否全为1就行。这种模式在按键去抖、通信帧同步里到处可见。软件和硬件对同一思想的不同实现做到后面会发现滑动窗口这个模型贯穿了很多领域。// Verilog 4点滑动窗口平均滤波 module slid_win_avg #(parameter WIDTH 4)( input clk, input rst_n, input [7:0] data_in, output [7:0] avg_out ); reg [7:0] buf0, buf1, buf2, buf3; // 每个时钟上升沿数据链向右移动 always (posedge clk or negedge rst_n) begin if (!rst_n) begin buf0 0; buf1 0; buf2 0; buf3 0; end else begin buf3 data_in; buf2 buf3; buf1 buf2; buf0 buf1; end end wire [9:0] sum buf0 buf1 buf2 buf3; assign avg_out sum[9:2]; // 除以4右移两位 endmodule硬件事物要额外留意数据有效信号。上面代码里的always块每个时钟都移入数据如果数据不是每个时钟都有效得再加一个data_valid信号只有有效时寄存器才移位。否则空白周期会把无效数据也移进窗口导致输出被拉偏。很多第一次写滑动窗口滤波的硬件初学者会在测试平台上发现波形异常一半是这个问题。5. 排查实录那些让人调一晚上的边界问题5.1 数组越界和left超过right的混乱现场无重复最长子串这道题我第一次提交时在循环里写的是if而不是while导致字符串只有一个字符且该字符出现两次时left没越过重复字符窗口永远带着重复字符输出就是错的。后来改成while后还有一个隐患如果窗口内只有这个重复字符left会一直右移到right1这时窗口为空freq表清空。代码逻辑在这个场景下应该返回长度1但如果后续代码没处理left right的情况就会出错。我的排查方法是专门列一个计算尺一样的测试清单空串、单字符、所有字符都相同、所有字符都不同、目标t比s还长、窗口正好覆盖整个数组。这些边界不是碰运气撞出来的是你必须写代码前就在纸上想清楚的。很多线上bug看起来诡异追根溯源就是窗口左指针超过了右指针这时候窗口已经空了任何对空窗口的统计操作都没有意义。5.2 最小覆盖子串里的count错位最小覆盖子串最容易出问题的是count加一和减一的时机。我第一版在加一的时候用的是window[c] need[c]而不是等于结果t里有两个A时窗口里有两个A会加两次count最后count needCnt窗口永远不合法答案为空。改成等于后再加入多余的A不会影响count。同样收缩时减一也必须是window[lc] need[lc]两个条件写反一测就崩。调试这个问题的通用技巧是“打点观察”在add和remove的每个分支打印字符、计数、count和当前窗口左右边界。我在本地跑数据a、ab、aa、aab、ADOBECODEBANC这些用例时把所有状态打出来对比很快就能锁定count错在哪个分支。断点调试看变量也可以但打印日志更适合这种循环几百次的数据流问题。5.3 整数溢出和返回值处理长度最小的子数组题目数组元素可能是大整数target也可能很大。如果用int存sum累加过程中可能溢出变成负数导致while条件判断永远不满足最后返回错误结果。C语言里我习惯用long long存sum或者累加前判断sum target - nums[right]来避免无意义累加。这类问题对Java和Python选手无感但对C/C做题的人非常现实面试时多用C的话一定要有这层意识。返回值还有一个经典坑找不到符合条件的窗口时返回什么。题目要求返回0、返回空串、返回-1不同题不同约定。我的建议是写一个全局的“return ans INF ? EMPTY : ans”用哨兵值统一处理避免每道题都写一遍边界判断过程中漏一个就错了。5.4 调试滑动窗口的通用技巧先跑小样例再跑大样例滑动窗口题目的调试有固定节奏。先不急着上编译器拿一支笔把数据从头走一遍左右指针、窗口状态、答案每一步更新都写在纸上。走完两个典型用例基本就能把代码逻辑理清楚。然后再上电脑先用小用例验证每个步骤再跑大数组验证复杂度和结果。最后跑性能极端的用例比如100万个全相同元素确认不会超时和溢出。还有个很实用的经验把代码里left和right的移动次数分别累加最后打印出来。正常情况下left移动次数加上right移动次数应该在2n左右。如果某一步明显多了一个数量级比如left停了right疯狂加一或者left反复来回那多半是收缩条件写错或者状态没有正确重置。这个统计手段帮我在调最小覆盖子串时快速确认了复杂度退化的问题后来我把它固化成了调试模板的一部分。另外我建议刷滑动窗口题时把每道题的“窗口合法条件”写成一行的注释放在代码顶部。比如“无重复子串freq[c] 1”“最小覆盖count needCnt”。这样过两周回看代码一眼就知道当时是怎么想的。窗口条件就是滑动窗口题的灵魂注释写清楚复习效率翻倍。最后再分享一个小技巧滑动窗口和双指针类题目如果一时想不明白到底该什么时候移动哪个指针就假设自己拿着一个放大镜在数据流上移动。放大镜覆盖的是“当前可能的答案区域”left是放大镜的左边缘right是右边缘。每当数据流移动一步判断放大镜里的内容是否符合题目要求不符合就调整左边缘符合就记录答案。这个形象化的过程帮我解决过不少模糊的边界情况如果你也在滑动窗口的变体里绕晕过不妨也试试把这个画面感移植到自己脑子里。