1. 为什么双指针和滑动窗口是面试与工程里的常客先从一个现象说起力扣上标注“通过率不高”的题十有七八都能用双指针或滑动窗口解。而你在实际写业务代码时凡是涉及“连续子数组”“子串统计”“窗口聚合”的场景最后落地成高效方案时绕来绕去也总会回到这两个思路上来。这不是巧合。它们的本质是同一种优化思想通过移动指针来维护一个区间把原本需要反复扫描的暴力过程压缩成一次或有限次的遍历把时间复杂度从 O(n²) 甚至 O(n³) 降下来。很多初学者会觉得“这两个东西是两种算法”其实更准确的说法是滑动窗口是双指针的一种特殊形态是双指针思想在“连续子区间”问题上的特化应用。理解了这层关系你再看题目就不会在两个名字之间摇摆。1.1 暴力解法到底慢在哪举个例子给你一个数组找出所有连续子数组中满足“和大于等于 target”的最短长度。最直觉的做法是枚举所有起点 i 和终点 j对每个区间求和这样复杂度是 O(n²)如果求和的时候再逐项累加那就是 O(n³)。暴力慢的原因有三点重复计算区间 [i, j] 和 [i1, j] 之间的公共部分被反复求和没有复用。无法利用单调性一旦明确“当前窗口已经满足条件”其实没必要再继续扩大右边界可以直接收缩左边界但暴力枚举不会利用这个信息。无效中间态很多子区间根本不可能成为答案但仍然被完整遍历了一遍。双指针和滑动窗口的每一招本质上都是针对这三点的“定向打击”用指针移动代替重新枚举用区间状态复用代替重复计算用条件判断剪掉无效区间。1.2 它们分别适合解决什么问题从应用场景上区分双指针更宽泛适合有序数组的查找问题两数之和、三数之和、链表中的环检测与中点查找、需要“两头夹逼”的场景。滑动窗口更聚焦只处理连续子区间/子串的问题。它的特征是题目里往往有“连续”“相邻”“覆盖”这类限定词而且窗口内的状态可以随着左右指针的移动增量更新。很多刷了一段时间题的人会出现一个困惑拿到一道题不知道该用双指针还是滑动窗口也不知道该用滑动窗口还是动态规划。我的判断标准很简单先看它要求的答案是不是一个连续区间的某个属性长度、和、覆盖情况、极值如果是就往滑动窗口上想如果问题是有序性查找或者链表操作就往双指针上想。2. 双指针的三条主流套路与判题场景双指针不是单一的模板它下边至少可以分为三个流派相向指针、快慢指针、同向指针。每一种都有自己固定的适用场景和一个经典的“骨架代码”你把这三种骨架背熟遇到新题时先判断属于哪一类再往里边套条件远比现场硬想高效。2.1 相向指针有序数组的两头夹逼相向指针最经典的应用是有序数组的“两数之和”问题。给定一个升序排列的数组找出两个数让它们的和等于 target。暴力做法是双重循环但如果你利用“数组有序”这个信息就能用两个指针分别指向数组头和尾根据当前和与 target 的关系决定移动当前和偏大说明右边指针指的数和任何左边的数相加都偏大右指针左移当前和偏小说明左边指针的数太小左指针右移相等直接返回。这个过程的复杂度是 O(n)每轮只移动一次指针不会回头。它的核心思想是在有序前提下指针移动一定不会错过可能的组合因为移动方向等价于“排除了一整批不可能的解”。def two_sum_sorted(nums, target): left, right 0, len(nums) - 1 while left right: current nums[left] nums[right] if current target: return [left, right] if current target: left 1 else: right - 1 return [-1, -1]这套骨架延伸出去能打很多题三数之和定一个数剩下两个用相向指针找、盛最多水的容器短板理论哪边短移哪边、接雨水两侧最大高度的维护。它们有个共同点都是通过指针相向移动逐步缩小搜索空间。2.2 快慢指针链表里的追逐问题快慢指针严格来说是双指针的一种但它的两个指针通常从同一起点出发一个跑得快、一个跑得慢用速度差制造相遇条件。最常见的应用是判断链表是否有环——Floyd 判圈算法。原理不复杂如果有环快指针每次走两步、慢指针每次走一步进入环之后两者必然会在有限步内相遇如果没环快指针会先碰到链表末尾的 None。def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False除了判环快慢指针还常用于寻找链表的中间节点、寻找链表中倒数第 k 个节点。后者有个很巧的变体让快指针先走 k 步然后快慢指针同步前进快指针到达末尾时慢指针正好指向倒数第 k 个节点。这种“先拉开距离再同步移动”的思路本质上是在用指针之间的距离差传递位置信息。2.3 同向指针滑动窗口的底座第三种是同向指针两个指针都从左侧出发一前一后向后移动。它的典型应用场景是“有序数组中找满足条件的区间”而无序数组中找连续子区间时同向双指针稍加改造就是滑动窗口。比如合并两个有序数组、寻找两个有序数组的交集都是同向指针的戏份。两个指针分别指向两个数组谁小谁先走值相等就记录并同时前进。这类题的核心是“哪个指针移动取决于当前元素的大小关系”和滑动窗口的“是否移动取决于窗口状态是否满足条件”有区别但共享同一套“指针永不回头”的底层逻辑。为了帮你快速定位把三种双指针的适用场景整理成一张表指针类型典型场景移动依据时间复杂度相向指针有序数组查找、求和、夹逼当前结果与目标的大小关系O(n)快慢指针链表判环、找中点、倒数第k个节点速度差/距离差O(n)同向指针有序数组合并、区间合并、滑动窗口当前元素大小/窗口状态O(n)你会发现所有双指针套路的时间复杂度都是 O(n)。它们之所以快是因为每个元素最多被某个指针经过有限次整体操作量和数组长度成正比而不是枚举所有组合的数量级。3. 滑动窗口的工作原理与通用框架滑动窗口能解决的问题有一个共同特征答案是一个连续的子数组或子串而且这个子区间的长度或内容满足某个约束条件。它做的事情非常朴素用 left 和 right 两个同向指针圈出一个区间right 负责扩张窗口left 负责收缩窗口。扩张的目的是让窗口“可行”收缩的目的是在“可行”的前提下寻找“最优”。全程用一个状态变量维护窗口内的信息避免每次重新计算。3.1 为什么窗口状态能增量维护这是滑动窗口高效的关键所在。你想象一个长度为 n 的数组窗口从空开始right 每次向右移动一格窗口就多纳入一个元素left 每次向右移动一格窗口就少掉一个元素。如果窗口内的“总和”“字符计数”“去重情况”在每次移动时只做一次加减或更新那么整趟下来每个元素进入窗口一次、离开窗口一次整体复杂度就是 O(n)。对比暴力法里每次都要重新枚举区间这个差距是决定性的。你甚至可以这么理解滑动窗口把“反复求同一个东西”变成了“维护一个一直在变化的东西”。前者每次从零开始后者永远只做增量更新这就是优化的本质。3.2 一套能打大部分题的模板市面上流传的滑动窗口模板很多但万变不离其宗。我常用的框架是这样右指针不断右移把新元素加入窗口同时更新窗口状态。每次右移后检查窗口状态是否满足条件。如果满足条件尝试收缩左指针每收缩一步更新状态并记录当前窗口对应的答案。直到窗口状态不再满足条件停止收缩继续右移右指针。写成伪代码就是left 0 for right in range(n): # 1. 把 nums[right] 加入窗口更新状态 # 2. 当窗口状态满足条件时: while condition_satisfied: # 3. 记录/更新答案 # 4. 把 nums[left] 移出窗口更新状态 left 1这里有一个容易混淆的点到底是在收缩前记录答案还是在收缩后记录答案。我的经验是先想清楚你要的是“满足条件的窗口”还是“满足条件的最短/最长窗口”求最短窗口如最短覆盖子串、最小连续子数组和在收缩循环内部更新答案因为收缩后的窗口更短可能更优。求最长窗口如无重复字符的最长子串长度随右移增加通常右移时或收缩完成后更新答案均可但要注意窗口在任意时刻都应该合法。具体到每道题你只需要明确两件事窗口状态用什么数据结构维护、收缩条件怎么判断。这二者定下来题就解了一半。3.3 固定窗口与可变窗口的切换滑动窗口还有另一个维度窗口长度是固定的还是可变的。固定窗口常用于“每 k 个元素一组”的统计问题。比如计算数组中所有长度为 k 的子数组的最大平均值。此时 right 每次右移一格、left 也跟着右移一格窗口像一个固定长度的传送带始终维护最近的 k 个元素。状态更新是加一个新元素、减一个旧元素。可变窗口则更灵活窗口长度取决于约束条件是否满足。比如“和大于等于 target 的最短子数组”right 一直扩张直到窗口和超过 target然后收缩 left 找最短。可变窗口的模板就是上一节那个通用框架。固定窗口和可变窗口的切换在真实题目中经常出现。我建议你遇到题目时先判断窗口长度有没有被题目明确指定有就是固定窗口没有就是可变窗口。明确这一点后再决定收缩逻辑怎么写。4. 高频题型全拆解四道题吃透滑动窗口我最初学滑动窗口时最大的困惑是“模板背下来了但遇到新题还是不知道状态怎么维护”。后来刷多了才发现滑动窗口的题目看着五花八门其实状态维护就几种哈希表计数、集合去重、单调队列、纯数值累加。下面用四道经典题把这四种状态维护方式各讲一遍代码和思路都给你可以直接照着敲。4.1 最小覆盖子串哈希表计数加双指针收缩题目要求给你一个字符串 s 和一个字符串 t返回 s 中涵盖 t 所有字符的最小子串。如果不存在返回空字符串。这道题是滑动窗口里的“集大成者”。窗口状态用两个哈希表维护一个记录 t 中每个字符的需求量一个记录当前窗口中各字符的存量然后通过一个变量formed记录当前窗口中有多少个字符已经达到了需求数量。窗口扩张时如果某个字符的存量等于需求量formed加一窗口收缩时如果存量降到了需求量以下formed减一。只有当formed等于 t 中不重复字符数时窗口才是“覆盖”状态此时不断收缩左指针找最短。def min_window(s, t): from collections import Counter, defaultdict need Counter(t) window defaultdict(int) formed 0 required len(need) left 0 min_len float(inf) min_left 0 for right, ch in enumerate(s): window[ch] 1 if ch in need and window[ch] need[ch]: formed 1 while formed required: if right - left 1 min_len: min_len right - left 1 min_left left left_ch s[left] window[left_ch] - 1 if left_ch in need and window[left_ch] need[left_ch]: formed - 1 left 1 return if min_len float(inf) else s[min_left:min_left min_len]这段代码里有几个细节值得注意。一是formed只在“恰好达到”和“恰好低于”需求时变化而不是每次增减都变这样可以避免频繁比较哈希表二是在收缩循环内部更新答案因为覆盖状态下窗口更短才可能更优三是用defaultdict避免访问不存在的 key 时报错。这道题覆盖了滑动窗口最核心的思维确定原子状态字符计数、复合状态formed和收缩条件formed required剩下的就是套模板。4.2 无重复字符的最长子串Set 维护窗口合法题目要求给定一个字符串找出其中不含有重复字符的最长子串的长度。这道题是很多人接触滑动窗口的第一道题状态维护方式非常直观用一个集合记录当前窗口内的字符。右指针扩张时如果新字符已经在集合里说明窗口不合法收缩左指针逐个删除集合里的字符直到把重复字符赶出窗口再把新字符加进去。def length_of_longest_substring(s): seen set() left 0 ans 0 for right, ch in enumerate(s): while ch in seen: seen.remove(s[left]) left 1 seen.add(ch) ans max(ans, right - left 1) return ans这道题里最容易踩的坑是收缩循环用while ch in seen而不是while left right。你要做的不是把整个窗口清空而是只把重复字符及其左侧的所有字符全部移出窗口。想象一下字符串 “abcba”走到最后一个 a 时窗口里是 “bcb”你要把 b 和 c 都踢出去只留最后的 a这时候光删掉一个字符是不够的。还有一个可以优化的点用数组last_occurrence记录每个字符上次出现的位置遇到重复字符时直接把 left 跳到上次出现位置的下一个这样可以省掉 while 循环让整体操作更接近 O(n) 的常数级别。不过对实际刷题来说Set 版本已经够用优化版本的代码反而更难读懂。4.3 滑动窗口最大值单调队列才是真正的主角题目要求给定整数数组 nums 和一个大小为 k 的滑动窗口窗口每次向右移动一位返回每个窗口中的最大值。这是滑动窗口里思维方式最不一样的一道题。前面几道题的状态维护都是在“计数”或“去重”而这道题要的是窗口内的最大值——如果你每次移动窗口都重新扫一遍找最大值复杂度会退化到 O(nk)。正确做法是维护一个单调递减的双端队列。队列里存的是数组下标从队首到队尾对应元素的值严格递减。这样队首永远是当前窗口的最大值。窗口右移时把新元素从队尾加入加入前把所有比它小的元素从队尾弹出窗口左移时如果队列队首的下标超出了窗口范围把队首弹出。from collections import deque def max_sliding_window(nums, k): q deque() ans [] for i, x in enumerate(nums): while q and nums[q[-1]] x: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: ans.append(nums[q[0]]) return ans这段代码的美妙之处在于队列里的元素虽然是递减的但每个元素只进队一次、出队一次总复杂度 O(n)。比每次重新找最大值的 O(nk) 不知道高明到哪里去了。我当时学这个题时有个疑问为什么队首过期时只需要检查q[0] i - k而不是循环弹出所有过期元素原因是窗口每次只左移一格所以每轮最多只有一个元素会离开窗口检查一次队首就够了。这个细节能帮你在写代码时少很多不必要的循环。这道题有一种衍生题型滑动窗口最小值只需把单调队列改成递增就行代码几乎一样就是比较符号反过来。你可以把两个题放在一起刷加深对单调队列的理解。4.4 长度最小的子数组最短可行窗口的经典写法题目要求给定一个正整数数组 nums找出该数组中满足“其和大于等于 target”的长度最小的连续子数组并返回其长度。这是“纯数值累加”型状态维护的典型。窗口状态就是一个变量window_sum右指针扩张时累加收缩时减少。收缩条件和前面几道题略有不同不是“达到某种状态”而是“窗口和仍然大于等于 target”。def min_subarray_len(target, nums): left 0 window_sum 0 ans float(inf) for right, x in enumerate(nums): window_sum x while window_sum target: ans min(ans, right - left 1) window_sum - nums[left] left 1 return ans if ans ! float(inf) else 0这道题的关键是在 while 循环里收缩每收缩一次就尝试更新一次答案。因为窗口和一旦达到 target继续扩张只会让长度更长不可能更优所以必须在收缩过程中找最短。如果你把这道题和“最小覆盖子串”放在一起对比会发现它们的框架几乎一模一样右移扩展、条件满足后收缩、收缩时更新答案。区别只是状态维护从“字符计数”变成了“数值累加”。这说明滑动窗口的思维是统一的命题人换的只是窗口内的状态和条件不是算法本身。还有两道衍生题字符串的排列、找所有字母异位词。它们本质上都是固定窗口长度的滑动窗口配合哈希表计数就能解。建议你在学完这四道题之后自己动手写一遍然后再去做这两道衍生题基本就是顺水推舟的事。5. 滑动窗口在真实工程里到底怎么落地聊完算法题再来说点更实际的东西。很多人刷完题会有一个疑惑这些滑动窗口的题目除了面试平时写业务代码真的用得上吗答案是不仅用得上而且到处都是。你平时可能没意识到是因为工程里的叫法不叫“滑动窗口”而叫“窗口统计”“流式聚合”“限流计数”。但内核是一模一样的。5.1 限流器里的滑动窗口从固定窗口到滑动日志系统设计里最常见的限流算法用的就是滑动窗口的变体。固定窗口计数器实现起来最简单把时间切成固定大小的窗口比如每秒每个窗口内维护一个计数器超过阈值就拒绝请求。但固定窗口有个很明显的缺陷——窗口边界附近可能出现“两倍流量”的漏洞。比如限流规则是 1 秒内最多 10 个请求第 0.9 秒来了 10 个第 1.1 秒又来了 10 个虽然单看每秒都没超但 0.2 秒内实际通过了 20 个请求。滑动窗口计数器可以缓解这个问题。它记录当前窗口内的时间戳每次新请求到来时把所有早于“当前时间 - 窗口大小”的时间戳清掉然后统计剩余数量是否超过阈值。这个做法和算法题里的滑动窗口模板几乎一一对应时间戳列表就是窗口状态过期时间戳的清理就是 left 指针的收缩。class SlidingWindowRateLimiter: def __init__(self, max_requests, window_seconds): self.max_requests max_requests self.window_seconds window_seconds self.timestamps [] def allow(self): now time.time() while self.timestamps and self.timestamps[0] now - self.window_seconds: self.timestamps.pop(0) if len(self.timestamps) self.max_requests: self.timestamps.append(now) return True return False这个实现还能再优化比如用collections.deque代替列表来保证队首弹出是 O(1)。但从思路上你已经能看出工程中的限流器和刷题时的滑动窗口是同一种生物。5.2 滑动窗口滤波信号处理里的移动平均与中值滤波热搜词里有不少“滑动窗口滤波”“滑动窗口滤波模型”“滑动窗口滤波 verilog”这说明硬件和信号处理方向的开发者也在大量关注这个概念。滑动窗口滤波的原理和算法题里的滑动窗口几乎一模一样用一个固定长度的窗口在数据序列上滑动每次取窗口内数据的一个统计量作为当前输出。最常见的是滑动平均滤波就是取窗口内元素平均值等价于算法题里的“固定窗口求均值”。它对高频噪声有天然的平滑作用但也会引入延迟这就是热搜里“滑动窗口滤波器延迟”这个关键词的来源——窗口越长平滑效果越好但输出相对真实信号的滞后也越明显。另一种常见的是滑动中值滤波取窗口内元素的中位数它对脉冲噪声比如传感器突然跳变的抑制能力比均值强很多。实现上如果数据量不大可以直接对窗口排序取中值如果性能要求高可以用两个堆来维护一个能动态求中位数的窗口这个题目在力扣上有原题叫“数据流的中位数”但用滑动窗口版本实现更贴近真实工程场景。在 Verilog/FPGA 实现场景里滑动窗口滤波器对应的是“移位寄存器 加法器树”的硬件结构。窗口里的数据被存进一排寄存器每个时钟周期拍一个数据进、弹一个数据出然后并行求和或排序。这个结构里的“移位寄存器”本质上就是算法题里的 left/right 指针只是变成了硬件流水线的形式。5.3 流式数据统计仪表盘上的每分钟请求数你在监控系统上看到的“最近 5 分钟请求量”“最近 1 小时错误率”这类指标底层大多也是滑动窗口。假设你要统计“过去 5 分钟内每分钟的错误率”传统做法是每来一条错误日志就查一次数据库把过去 5 分钟的数据拉出来聚合这显然很慢。用滑动窗口的思路你只需要维护一个长度为 5 的环形数组每个元素记录对应分钟的错误数同时用一个变量记录窗口内总错误数。新数据进来时覆盖最旧的那个格子更新总和就能在 O(1) 时间内得到 5 分钟的错误总数。class MetricsWindow: def __init__(self, size): self.size size self.bucket [0] * size self.total 0 self.current_index 0 def add(self, value, current_bucket_index): if current_bucket_index 0: return idx current_bucket_index % self.size self.total - self.bucket[idx] self.bucket[idx] value self.total value这段代码虽然简单但它体现了一个重要思路固定窗口只要维护好“淘汰最旧元素”的逻辑更新代价就是 O(1)不需要每次全量聚合。这在数据量大的时候可能就是从“跑不动”到“几乎零成本”的差别。6. 实战中我踩过的坑与看得见的效率边界讲了这么多原理和代码最后聊点实在的我自己在学这两个算法、以及在工程里用它们时踩过的坑。这些细节代码模板里不会写但你可能迟早会遇到。6.1 边界条件和高频错误清单滑动窗口代码看起来不长但边界条件特别容易写错。我整理了几个我反复踩过的坑希望你第一次学就能避开忘记处理空输入。很多滑动窗口题目输入可能为空数组或空字符串。我刚开始刷题时经常因为没写if not nums: return ...导致索引越界。建议每次写好主逻辑后先花十秒钟想一下空输入时会发生什么。收缩循环用 if 还是 while。如果你在求“最短覆盖窗口”收缩条件在某一轮里可能只需要收缩一次也可能需要连续收缩很多次。绝大多数情况下都应该用 while而不是 if。用 if 的后果是窗口明明还能收缩得更短你却提前停住了。只有一个例外固定窗口滑动时每轮最多收缩一次用 if 就够了。记录答案的位置写错。这是新手最容易搞混的地方。缩之前的窗口可能是唯一满足条件的窗口缩之后可能已经不再满足条件。你需要先想清楚题目求的是“满足条件的最长/最短窗口”再决定在哪个位置更新答案。最稳妥的办法是写完代码后手动跑一个简单例子逐行走一遍看答案是在哪一行被更新的是否符合你的预期。哈希表重复计数。在最小覆盖子串那道题里如果用window[ch] need[ch]判断“达到需求”要注意每种字符只在“恰好等于”的那一次让formed加一。如果你每轮都统计一遍哈希表里的匹配字符数复杂度就退化了。单调队列的队首过期。滑动窗口最大值里队首超出窗口左边界时必须弹出但只需要检查一次。如果你写成 while 循环弹出所有过期元素也没什么问题但效率略低而且代码更啰嗦。6.2 时间复杂度好在哪里很多人背住了“滑动窗口是 O(n)”但没想过为什么是 O(n)。核心在于每个元素进入窗口一次、离开窗口一次。right 指针一路扫到尾不会回头left 指针虽然可能多次移动但最多也只能从 0 一路移动到 n。两者加起来总操作次数严格不超过 2n所以均摊复杂度是 O(n)。对比一下暴力解法的 O(n²)当数据量是 10 万时差别是 10 万次操作和 100 亿次操作的差别。这也解释了为什么很多实时系统里状态维护必须要用滑动窗口或差不多的增量更新方式——全量重算在大数据量下是扛不住的。6.3 面试中怎么讲思路才能加分如果你是为了面试准备这块内容我建议你在描述解题思路时不要上来就扔模板而是按这个顺序讲先说暴力解。告诉面试官朴素做法是枚举所有区间复杂度是 O(n²)空间复杂度 O(1)。这一步能让对方确认你理解问题本身。再说瓶颈。指出暴力解慢的原因是重复计算、没有利用区间连续性这个信息。然后引入滑动窗口。说明“既然答案是连续子区间那我可以维护一个窗口让左右指针滑动把重复扫描变成增量更新”。最后落到状态维护。具体到这道题窗口状态用什么记录、什么时候收缩、收缩时怎么更新答案。这个叙述顺序的价值在于它不是背公式而是在展示你从问题出发推导算法的能力。面试官想看到的是思考过程而不是一个能默写模板的复读机。如果你刚开始刷这部分内容我建议按下面这个顺序循序渐进先做“无重复字符的最长子串”理解窗口合法与收缩再做“长度最小的子数组”理解收缩时更新答案然后做“最小覆盖子串”理解多状态维护最后做“滑动窗口最大值”理解单调队列。四道题做完双指针和滑动窗口的主体框架就在你脑子里成型了再去外面打其他同类型题目基本就是换壳不换芯。刷题这事没有捷径但找对套路能让你少走很多弯路。
双指针算法与滑动窗口模板：从力扣高频题到工程实战
1. 为什么双指针和滑动窗口是面试与工程里的常客先从一个现象说起力扣上标注“通过率不高”的题十有七八都能用双指针或滑动窗口解。而你在实际写业务代码时凡是涉及“连续子数组”“子串统计”“窗口聚合”的场景最后落地成高效方案时绕来绕去也总会回到这两个思路上来。这不是巧合。它们的本质是同一种优化思想通过移动指针来维护一个区间把原本需要反复扫描的暴力过程压缩成一次或有限次的遍历把时间复杂度从 O(n²) 甚至 O(n³) 降下来。很多初学者会觉得“这两个东西是两种算法”其实更准确的说法是滑动窗口是双指针的一种特殊形态是双指针思想在“连续子区间”问题上的特化应用。理解了这层关系你再看题目就不会在两个名字之间摇摆。1.1 暴力解法到底慢在哪举个例子给你一个数组找出所有连续子数组中满足“和大于等于 target”的最短长度。最直觉的做法是枚举所有起点 i 和终点 j对每个区间求和这样复杂度是 O(n²)如果求和的时候再逐项累加那就是 O(n³)。暴力慢的原因有三点重复计算区间 [i, j] 和 [i1, j] 之间的公共部分被反复求和没有复用。无法利用单调性一旦明确“当前窗口已经满足条件”其实没必要再继续扩大右边界可以直接收缩左边界但暴力枚举不会利用这个信息。无效中间态很多子区间根本不可能成为答案但仍然被完整遍历了一遍。双指针和滑动窗口的每一招本质上都是针对这三点的“定向打击”用指针移动代替重新枚举用区间状态复用代替重复计算用条件判断剪掉无效区间。1.2 它们分别适合解决什么问题从应用场景上区分双指针更宽泛适合有序数组的查找问题两数之和、三数之和、链表中的环检测与中点查找、需要“两头夹逼”的场景。滑动窗口更聚焦只处理连续子区间/子串的问题。它的特征是题目里往往有“连续”“相邻”“覆盖”这类限定词而且窗口内的状态可以随着左右指针的移动增量更新。很多刷了一段时间题的人会出现一个困惑拿到一道题不知道该用双指针还是滑动窗口也不知道该用滑动窗口还是动态规划。我的判断标准很简单先看它要求的答案是不是一个连续区间的某个属性长度、和、覆盖情况、极值如果是就往滑动窗口上想如果问题是有序性查找或者链表操作就往双指针上想。2. 双指针的三条主流套路与判题场景双指针不是单一的模板它下边至少可以分为三个流派相向指针、快慢指针、同向指针。每一种都有自己固定的适用场景和一个经典的“骨架代码”你把这三种骨架背熟遇到新题时先判断属于哪一类再往里边套条件远比现场硬想高效。2.1 相向指针有序数组的两头夹逼相向指针最经典的应用是有序数组的“两数之和”问题。给定一个升序排列的数组找出两个数让它们的和等于 target。暴力做法是双重循环但如果你利用“数组有序”这个信息就能用两个指针分别指向数组头和尾根据当前和与 target 的关系决定移动当前和偏大说明右边指针指的数和任何左边的数相加都偏大右指针左移当前和偏小说明左边指针的数太小左指针右移相等直接返回。这个过程的复杂度是 O(n)每轮只移动一次指针不会回头。它的核心思想是在有序前提下指针移动一定不会错过可能的组合因为移动方向等价于“排除了一整批不可能的解”。def two_sum_sorted(nums, target): left, right 0, len(nums) - 1 while left right: current nums[left] nums[right] if current target: return [left, right] if current target: left 1 else: right - 1 return [-1, -1]这套骨架延伸出去能打很多题三数之和定一个数剩下两个用相向指针找、盛最多水的容器短板理论哪边短移哪边、接雨水两侧最大高度的维护。它们有个共同点都是通过指针相向移动逐步缩小搜索空间。2.2 快慢指针链表里的追逐问题快慢指针严格来说是双指针的一种但它的两个指针通常从同一起点出发一个跑得快、一个跑得慢用速度差制造相遇条件。最常见的应用是判断链表是否有环——Floyd 判圈算法。原理不复杂如果有环快指针每次走两步、慢指针每次走一步进入环之后两者必然会在有限步内相遇如果没环快指针会先碰到链表末尾的 None。def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False除了判环快慢指针还常用于寻找链表的中间节点、寻找链表中倒数第 k 个节点。后者有个很巧的变体让快指针先走 k 步然后快慢指针同步前进快指针到达末尾时慢指针正好指向倒数第 k 个节点。这种“先拉开距离再同步移动”的思路本质上是在用指针之间的距离差传递位置信息。2.3 同向指针滑动窗口的底座第三种是同向指针两个指针都从左侧出发一前一后向后移动。它的典型应用场景是“有序数组中找满足条件的区间”而无序数组中找连续子区间时同向双指针稍加改造就是滑动窗口。比如合并两个有序数组、寻找两个有序数组的交集都是同向指针的戏份。两个指针分别指向两个数组谁小谁先走值相等就记录并同时前进。这类题的核心是“哪个指针移动取决于当前元素的大小关系”和滑动窗口的“是否移动取决于窗口状态是否满足条件”有区别但共享同一套“指针永不回头”的底层逻辑。为了帮你快速定位把三种双指针的适用场景整理成一张表指针类型典型场景移动依据时间复杂度相向指针有序数组查找、求和、夹逼当前结果与目标的大小关系O(n)快慢指针链表判环、找中点、倒数第k个节点速度差/距离差O(n)同向指针有序数组合并、区间合并、滑动窗口当前元素大小/窗口状态O(n)你会发现所有双指针套路的时间复杂度都是 O(n)。它们之所以快是因为每个元素最多被某个指针经过有限次整体操作量和数组长度成正比而不是枚举所有组合的数量级。3. 滑动窗口的工作原理与通用框架滑动窗口能解决的问题有一个共同特征答案是一个连续的子数组或子串而且这个子区间的长度或内容满足某个约束条件。它做的事情非常朴素用 left 和 right 两个同向指针圈出一个区间right 负责扩张窗口left 负责收缩窗口。扩张的目的是让窗口“可行”收缩的目的是在“可行”的前提下寻找“最优”。全程用一个状态变量维护窗口内的信息避免每次重新计算。3.1 为什么窗口状态能增量维护这是滑动窗口高效的关键所在。你想象一个长度为 n 的数组窗口从空开始right 每次向右移动一格窗口就多纳入一个元素left 每次向右移动一格窗口就少掉一个元素。如果窗口内的“总和”“字符计数”“去重情况”在每次移动时只做一次加减或更新那么整趟下来每个元素进入窗口一次、离开窗口一次整体复杂度就是 O(n)。对比暴力法里每次都要重新枚举区间这个差距是决定性的。你甚至可以这么理解滑动窗口把“反复求同一个东西”变成了“维护一个一直在变化的东西”。前者每次从零开始后者永远只做增量更新这就是优化的本质。3.2 一套能打大部分题的模板市面上流传的滑动窗口模板很多但万变不离其宗。我常用的框架是这样右指针不断右移把新元素加入窗口同时更新窗口状态。每次右移后检查窗口状态是否满足条件。如果满足条件尝试收缩左指针每收缩一步更新状态并记录当前窗口对应的答案。直到窗口状态不再满足条件停止收缩继续右移右指针。写成伪代码就是left 0 for right in range(n): # 1. 把 nums[right] 加入窗口更新状态 # 2. 当窗口状态满足条件时: while condition_satisfied: # 3. 记录/更新答案 # 4. 把 nums[left] 移出窗口更新状态 left 1这里有一个容易混淆的点到底是在收缩前记录答案还是在收缩后记录答案。我的经验是先想清楚你要的是“满足条件的窗口”还是“满足条件的最短/最长窗口”求最短窗口如最短覆盖子串、最小连续子数组和在收缩循环内部更新答案因为收缩后的窗口更短可能更优。求最长窗口如无重复字符的最长子串长度随右移增加通常右移时或收缩完成后更新答案均可但要注意窗口在任意时刻都应该合法。具体到每道题你只需要明确两件事窗口状态用什么数据结构维护、收缩条件怎么判断。这二者定下来题就解了一半。3.3 固定窗口与可变窗口的切换滑动窗口还有另一个维度窗口长度是固定的还是可变的。固定窗口常用于“每 k 个元素一组”的统计问题。比如计算数组中所有长度为 k 的子数组的最大平均值。此时 right 每次右移一格、left 也跟着右移一格窗口像一个固定长度的传送带始终维护最近的 k 个元素。状态更新是加一个新元素、减一个旧元素。可变窗口则更灵活窗口长度取决于约束条件是否满足。比如“和大于等于 target 的最短子数组”right 一直扩张直到窗口和超过 target然后收缩 left 找最短。可变窗口的模板就是上一节那个通用框架。固定窗口和可变窗口的切换在真实题目中经常出现。我建议你遇到题目时先判断窗口长度有没有被题目明确指定有就是固定窗口没有就是可变窗口。明确这一点后再决定收缩逻辑怎么写。4. 高频题型全拆解四道题吃透滑动窗口我最初学滑动窗口时最大的困惑是“模板背下来了但遇到新题还是不知道状态怎么维护”。后来刷多了才发现滑动窗口的题目看着五花八门其实状态维护就几种哈希表计数、集合去重、单调队列、纯数值累加。下面用四道经典题把这四种状态维护方式各讲一遍代码和思路都给你可以直接照着敲。4.1 最小覆盖子串哈希表计数加双指针收缩题目要求给你一个字符串 s 和一个字符串 t返回 s 中涵盖 t 所有字符的最小子串。如果不存在返回空字符串。这道题是滑动窗口里的“集大成者”。窗口状态用两个哈希表维护一个记录 t 中每个字符的需求量一个记录当前窗口中各字符的存量然后通过一个变量formed记录当前窗口中有多少个字符已经达到了需求数量。窗口扩张时如果某个字符的存量等于需求量formed加一窗口收缩时如果存量降到了需求量以下formed减一。只有当formed等于 t 中不重复字符数时窗口才是“覆盖”状态此时不断收缩左指针找最短。def min_window(s, t): from collections import Counter, defaultdict need Counter(t) window defaultdict(int) formed 0 required len(need) left 0 min_len float(inf) min_left 0 for right, ch in enumerate(s): window[ch] 1 if ch in need and window[ch] need[ch]: formed 1 while formed required: if right - left 1 min_len: min_len right - left 1 min_left left left_ch s[left] window[left_ch] - 1 if left_ch in need and window[left_ch] need[left_ch]: formed - 1 left 1 return if min_len float(inf) else s[min_left:min_left min_len]这段代码里有几个细节值得注意。一是formed只在“恰好达到”和“恰好低于”需求时变化而不是每次增减都变这样可以避免频繁比较哈希表二是在收缩循环内部更新答案因为覆盖状态下窗口更短才可能更优三是用defaultdict避免访问不存在的 key 时报错。这道题覆盖了滑动窗口最核心的思维确定原子状态字符计数、复合状态formed和收缩条件formed required剩下的就是套模板。4.2 无重复字符的最长子串Set 维护窗口合法题目要求给定一个字符串找出其中不含有重复字符的最长子串的长度。这道题是很多人接触滑动窗口的第一道题状态维护方式非常直观用一个集合记录当前窗口内的字符。右指针扩张时如果新字符已经在集合里说明窗口不合法收缩左指针逐个删除集合里的字符直到把重复字符赶出窗口再把新字符加进去。def length_of_longest_substring(s): seen set() left 0 ans 0 for right, ch in enumerate(s): while ch in seen: seen.remove(s[left]) left 1 seen.add(ch) ans max(ans, right - left 1) return ans这道题里最容易踩的坑是收缩循环用while ch in seen而不是while left right。你要做的不是把整个窗口清空而是只把重复字符及其左侧的所有字符全部移出窗口。想象一下字符串 “abcba”走到最后一个 a 时窗口里是 “bcb”你要把 b 和 c 都踢出去只留最后的 a这时候光删掉一个字符是不够的。还有一个可以优化的点用数组last_occurrence记录每个字符上次出现的位置遇到重复字符时直接把 left 跳到上次出现位置的下一个这样可以省掉 while 循环让整体操作更接近 O(n) 的常数级别。不过对实际刷题来说Set 版本已经够用优化版本的代码反而更难读懂。4.3 滑动窗口最大值单调队列才是真正的主角题目要求给定整数数组 nums 和一个大小为 k 的滑动窗口窗口每次向右移动一位返回每个窗口中的最大值。这是滑动窗口里思维方式最不一样的一道题。前面几道题的状态维护都是在“计数”或“去重”而这道题要的是窗口内的最大值——如果你每次移动窗口都重新扫一遍找最大值复杂度会退化到 O(nk)。正确做法是维护一个单调递减的双端队列。队列里存的是数组下标从队首到队尾对应元素的值严格递减。这样队首永远是当前窗口的最大值。窗口右移时把新元素从队尾加入加入前把所有比它小的元素从队尾弹出窗口左移时如果队列队首的下标超出了窗口范围把队首弹出。from collections import deque def max_sliding_window(nums, k): q deque() ans [] for i, x in enumerate(nums): while q and nums[q[-1]] x: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: ans.append(nums[q[0]]) return ans这段代码的美妙之处在于队列里的元素虽然是递减的但每个元素只进队一次、出队一次总复杂度 O(n)。比每次重新找最大值的 O(nk) 不知道高明到哪里去了。我当时学这个题时有个疑问为什么队首过期时只需要检查q[0] i - k而不是循环弹出所有过期元素原因是窗口每次只左移一格所以每轮最多只有一个元素会离开窗口检查一次队首就够了。这个细节能帮你在写代码时少很多不必要的循环。这道题有一种衍生题型滑动窗口最小值只需把单调队列改成递增就行代码几乎一样就是比较符号反过来。你可以把两个题放在一起刷加深对单调队列的理解。4.4 长度最小的子数组最短可行窗口的经典写法题目要求给定一个正整数数组 nums找出该数组中满足“其和大于等于 target”的长度最小的连续子数组并返回其长度。这是“纯数值累加”型状态维护的典型。窗口状态就是一个变量window_sum右指针扩张时累加收缩时减少。收缩条件和前面几道题略有不同不是“达到某种状态”而是“窗口和仍然大于等于 target”。def min_subarray_len(target, nums): left 0 window_sum 0 ans float(inf) for right, x in enumerate(nums): window_sum x while window_sum target: ans min(ans, right - left 1) window_sum - nums[left] left 1 return ans if ans ! float(inf) else 0这道题的关键是在 while 循环里收缩每收缩一次就尝试更新一次答案。因为窗口和一旦达到 target继续扩张只会让长度更长不可能更优所以必须在收缩过程中找最短。如果你把这道题和“最小覆盖子串”放在一起对比会发现它们的框架几乎一模一样右移扩展、条件满足后收缩、收缩时更新答案。区别只是状态维护从“字符计数”变成了“数值累加”。这说明滑动窗口的思维是统一的命题人换的只是窗口内的状态和条件不是算法本身。还有两道衍生题字符串的排列、找所有字母异位词。它们本质上都是固定窗口长度的滑动窗口配合哈希表计数就能解。建议你在学完这四道题之后自己动手写一遍然后再去做这两道衍生题基本就是顺水推舟的事。5. 滑动窗口在真实工程里到底怎么落地聊完算法题再来说点更实际的东西。很多人刷完题会有一个疑惑这些滑动窗口的题目除了面试平时写业务代码真的用得上吗答案是不仅用得上而且到处都是。你平时可能没意识到是因为工程里的叫法不叫“滑动窗口”而叫“窗口统计”“流式聚合”“限流计数”。但内核是一模一样的。5.1 限流器里的滑动窗口从固定窗口到滑动日志系统设计里最常见的限流算法用的就是滑动窗口的变体。固定窗口计数器实现起来最简单把时间切成固定大小的窗口比如每秒每个窗口内维护一个计数器超过阈值就拒绝请求。但固定窗口有个很明显的缺陷——窗口边界附近可能出现“两倍流量”的漏洞。比如限流规则是 1 秒内最多 10 个请求第 0.9 秒来了 10 个第 1.1 秒又来了 10 个虽然单看每秒都没超但 0.2 秒内实际通过了 20 个请求。滑动窗口计数器可以缓解这个问题。它记录当前窗口内的时间戳每次新请求到来时把所有早于“当前时间 - 窗口大小”的时间戳清掉然后统计剩余数量是否超过阈值。这个做法和算法题里的滑动窗口模板几乎一一对应时间戳列表就是窗口状态过期时间戳的清理就是 left 指针的收缩。class SlidingWindowRateLimiter: def __init__(self, max_requests, window_seconds): self.max_requests max_requests self.window_seconds window_seconds self.timestamps [] def allow(self): now time.time() while self.timestamps and self.timestamps[0] now - self.window_seconds: self.timestamps.pop(0) if len(self.timestamps) self.max_requests: self.timestamps.append(now) return True return False这个实现还能再优化比如用collections.deque代替列表来保证队首弹出是 O(1)。但从思路上你已经能看出工程中的限流器和刷题时的滑动窗口是同一种生物。5.2 滑动窗口滤波信号处理里的移动平均与中值滤波热搜词里有不少“滑动窗口滤波”“滑动窗口滤波模型”“滑动窗口滤波 verilog”这说明硬件和信号处理方向的开发者也在大量关注这个概念。滑动窗口滤波的原理和算法题里的滑动窗口几乎一模一样用一个固定长度的窗口在数据序列上滑动每次取窗口内数据的一个统计量作为当前输出。最常见的是滑动平均滤波就是取窗口内元素平均值等价于算法题里的“固定窗口求均值”。它对高频噪声有天然的平滑作用但也会引入延迟这就是热搜里“滑动窗口滤波器延迟”这个关键词的来源——窗口越长平滑效果越好但输出相对真实信号的滞后也越明显。另一种常见的是滑动中值滤波取窗口内元素的中位数它对脉冲噪声比如传感器突然跳变的抑制能力比均值强很多。实现上如果数据量不大可以直接对窗口排序取中值如果性能要求高可以用两个堆来维护一个能动态求中位数的窗口这个题目在力扣上有原题叫“数据流的中位数”但用滑动窗口版本实现更贴近真实工程场景。在 Verilog/FPGA 实现场景里滑动窗口滤波器对应的是“移位寄存器 加法器树”的硬件结构。窗口里的数据被存进一排寄存器每个时钟周期拍一个数据进、弹一个数据出然后并行求和或排序。这个结构里的“移位寄存器”本质上就是算法题里的 left/right 指针只是变成了硬件流水线的形式。5.3 流式数据统计仪表盘上的每分钟请求数你在监控系统上看到的“最近 5 分钟请求量”“最近 1 小时错误率”这类指标底层大多也是滑动窗口。假设你要统计“过去 5 分钟内每分钟的错误率”传统做法是每来一条错误日志就查一次数据库把过去 5 分钟的数据拉出来聚合这显然很慢。用滑动窗口的思路你只需要维护一个长度为 5 的环形数组每个元素记录对应分钟的错误数同时用一个变量记录窗口内总错误数。新数据进来时覆盖最旧的那个格子更新总和就能在 O(1) 时间内得到 5 分钟的错误总数。class MetricsWindow: def __init__(self, size): self.size size self.bucket [0] * size self.total 0 self.current_index 0 def add(self, value, current_bucket_index): if current_bucket_index 0: return idx current_bucket_index % self.size self.total - self.bucket[idx] self.bucket[idx] value self.total value这段代码虽然简单但它体现了一个重要思路固定窗口只要维护好“淘汰最旧元素”的逻辑更新代价就是 O(1)不需要每次全量聚合。这在数据量大的时候可能就是从“跑不动”到“几乎零成本”的差别。6. 实战中我踩过的坑与看得见的效率边界讲了这么多原理和代码最后聊点实在的我自己在学这两个算法、以及在工程里用它们时踩过的坑。这些细节代码模板里不会写但你可能迟早会遇到。6.1 边界条件和高频错误清单滑动窗口代码看起来不长但边界条件特别容易写错。我整理了几个我反复踩过的坑希望你第一次学就能避开忘记处理空输入。很多滑动窗口题目输入可能为空数组或空字符串。我刚开始刷题时经常因为没写if not nums: return ...导致索引越界。建议每次写好主逻辑后先花十秒钟想一下空输入时会发生什么。收缩循环用 if 还是 while。如果你在求“最短覆盖窗口”收缩条件在某一轮里可能只需要收缩一次也可能需要连续收缩很多次。绝大多数情况下都应该用 while而不是 if。用 if 的后果是窗口明明还能收缩得更短你却提前停住了。只有一个例外固定窗口滑动时每轮最多收缩一次用 if 就够了。记录答案的位置写错。这是新手最容易搞混的地方。缩之前的窗口可能是唯一满足条件的窗口缩之后可能已经不再满足条件。你需要先想清楚题目求的是“满足条件的最长/最短窗口”再决定在哪个位置更新答案。最稳妥的办法是写完代码后手动跑一个简单例子逐行走一遍看答案是在哪一行被更新的是否符合你的预期。哈希表重复计数。在最小覆盖子串那道题里如果用window[ch] need[ch]判断“达到需求”要注意每种字符只在“恰好等于”的那一次让formed加一。如果你每轮都统计一遍哈希表里的匹配字符数复杂度就退化了。单调队列的队首过期。滑动窗口最大值里队首超出窗口左边界时必须弹出但只需要检查一次。如果你写成 while 循环弹出所有过期元素也没什么问题但效率略低而且代码更啰嗦。6.2 时间复杂度好在哪里很多人背住了“滑动窗口是 O(n)”但没想过为什么是 O(n)。核心在于每个元素进入窗口一次、离开窗口一次。right 指针一路扫到尾不会回头left 指针虽然可能多次移动但最多也只能从 0 一路移动到 n。两者加起来总操作次数严格不超过 2n所以均摊复杂度是 O(n)。对比一下暴力解法的 O(n²)当数据量是 10 万时差别是 10 万次操作和 100 亿次操作的差别。这也解释了为什么很多实时系统里状态维护必须要用滑动窗口或差不多的增量更新方式——全量重算在大数据量下是扛不住的。6.3 面试中怎么讲思路才能加分如果你是为了面试准备这块内容我建议你在描述解题思路时不要上来就扔模板而是按这个顺序讲先说暴力解。告诉面试官朴素做法是枚举所有区间复杂度是 O(n²)空间复杂度 O(1)。这一步能让对方确认你理解问题本身。再说瓶颈。指出暴力解慢的原因是重复计算、没有利用区间连续性这个信息。然后引入滑动窗口。说明“既然答案是连续子区间那我可以维护一个窗口让左右指针滑动把重复扫描变成增量更新”。最后落到状态维护。具体到这道题窗口状态用什么记录、什么时候收缩、收缩时怎么更新答案。这个叙述顺序的价值在于它不是背公式而是在展示你从问题出发推导算法的能力。面试官想看到的是思考过程而不是一个能默写模板的复读机。如果你刚开始刷这部分内容我建议按下面这个顺序循序渐进先做“无重复字符的最长子串”理解窗口合法与收缩再做“长度最小的子数组”理解收缩时更新答案然后做“最小覆盖子串”理解多状态维护最后做“滑动窗口最大值”理解单调队列。四道题做完双指针和滑动窗口的主体框架就在你脑子里成型了再去外面打其他同类型题目基本就是换壳不换芯。刷题这事没有捷径但找对套路能让你少走很多弯路。
