滑动窗口（Sliding Window）算法指南：从 TCP 流量控制到 LeetCode 连续子数组问题

文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载滑动窗口是算法题解中处理连续子串连续子数组类问题的高频套路本质上是一种双指针two pointers技巧可将暴力枚举的 $O(N^2)$ 复杂度优化到 $O(N)$。本文以 leetcode 题解仓库滑动窗口专题为核心完整讲解滑动窗口的三种常见类型、固定窗口与可变窗口的指针维护规则、可直接套用的代码模板并结合仓库内 209. 长度最小的子数组、3. 无重复字符的最长子串、1004. 最大连续 1 的个数 III、978. 最长湍流子数组、1658. 将 x 减到 0 的最小操作数 等真实题解带你建立看到连续问题就想到滑动窗口的条件反射并掌握从暴力枚举出发一步步优化到 $O(N)$ 双指针解法的完整推导路径。长度最小的子数组滑动窗口过程示意图从 TCP 滑动窗口协议说起笔者最早接触滑动窗口一词是计算机网络中的滑动窗口协议Sliding Window Protocol。它是 TCP 协议的一种应用用于网络数据传输时的流量控制以避免拥塞的发生。发送方和接收方分别有一个窗口大小 w1 和 w2窗口大小可能会根据网络流量的变化而有所不同但是在更简单的实现中它们是固定的。窗口大小必须大于零才能进行任何操作。算法中的滑动窗口与之非常类似但适用场景更加广泛。实际上TCP 中的滑动窗口在某一时刻就是一个固定窗口大小的滑动窗口只是随着网络流量等因素的变化窗口大小也会随之改变。理解了这一层就不难理解算法中固定窗口与可变窗口的划分来源本质是同一套思路区别仅在实现细节。介绍滑动窗口解决什么问题滑动窗口是一种解决问题的思路和方法通常用来解决一些连续问题。所谓连续问题即题面中出现连续子串 xxxx连续子数组 xxxx这类描述的题目例如 LeetCode 的 209. 长度最小的子数组。只要题目求解的是连续子串 / 连续子数组就应该立刻联想到滑动窗口——能不能解决另说但这种敏感性是必须建立的。官方英文版文档slide-window.en.en.md也强调滑动窗口技巧又称双指针技巧可以在求解连续consecutive/contiguous元素的题目中帮助降低时间复杂度。常见套路三种窗口类型从类型上说滑动窗口题目主要有三种固定窗口大小Fixed Window Size窗口大小不固定求解最大的满足条件的窗口Variable Window, Maximum窗口大小不固定求解最小的满足条件的窗口Variable Window, Minimum上面的 209 题就属于这种后两种统称为可变窗口。不管哪种类型基本思路都是一样的不一样的仅仅是代码细节。固定窗口大小对于固定窗口只需要固定初始化左右指针 l 和 r分别表示窗口的左右顶点并且保证l 初始化为 0初始化 r使得 r - l 1 等于窗口大小同时移动 l 和 r判断窗口内的连续元素是否满足题目限定的条件4.1 如果满足再判断是否需要更新最优解如果需要则更新最优解返回或继续寻找更优4.2 如果不满足则继续寻找合适的窗口固定窗口的特征是左右指针同步平移窗口长度始终保持r - l 1不变因此关键在于每次平移后对窗口内信息的增量维护。典型的固定窗口题如 438. 找到字符串中所有字母异位词见下方题目列表窗口长度固定为 p 的长度滑动过程中只需维护字符频次计数。可变窗口大小对于可变窗口同样初始化左右指针 l 和 r分别表示窗口的左右顶点后面有所不同需要保证l 和 r 都初始化为 0r 指针移动一步向右扩展判断窗口内的连续元素是否满足题目限定的条件3.1 如果满足3.1.1 需要最优解时尝试通过移动 l 指针缩小窗口大小循环执行 3.13.1.2 否则返回当前解3.2 如果不满足则继续扩展形象地来看就是r 指针不停向右移动l 指针仅仅在窗口满足条件之后才会移动起到窗口收缩的效果。即先移动 r 找到一个合适窗口再移动 l 去缩小窗口、逼近最优解。可变窗口的典型代表就是求最小满足条件窗口的 209. 长度最小的子数组以及求最大满足条件窗口的 3. 无重复字符的最长子串无重复字符的最长子串滑动窗口动画模板代码从伪代码到可运行实现伪代码仓库中文版文档给出了通用于三种类型的伪代码框架初始化慢指针 0 初始化 ans for 快指针 in 可迭代集合 更新窗口内信息 while 窗口内不符合题意 扩展或者收缩窗口 慢指针移动 更新答案 返回 ans这个框架的关键在于两层循环的分工外层for循环负责右指针快指针的扩展内层while循环负责左指针慢指针的收缩更新窗口内信息与更新答案的位置决定了解法是求最大还是求最小窗口。代码209 题的 Python 模板以下是 209. 长度最小的子数组 的 Python 解法也是可变窗口求最小的标准模板class Solution: def minSubArrayLen(self, s: int, nums: List[int]) - int: l total 0 ans len(nums) 1 for r in range(len(nums)): total nums[r] while total s: ans min(ans, r - l 1) total - nums[l] l 1 return 0 if ans len(nums) 1 else ans逐步拆解这段模板l total 0左指针与窗口内元素和均初始化为 0ans len(nums) 1初始化答案为不可能达到的较大值N1用是否仍等于该值来判断是否存在合法解这也是最后return 0 if ans len(nums) 1 else ans的判定依据for r in range(len(nums))右指针向右扩展同时total nums[r]增量维护窗口和——这是更新窗口内信息while total s窗口满足条件时先更新最小长度ans min(ans, r - l 1)再total - nums[l]; l 1收缩左边界——这是while 窗口内不符合题意/或满足时收缩窗口最终若ans仍是初始值说明不存在和 ≥ s 的连续子数组返回 0。复杂度分析时间复杂度 $O(N)$N 为数组大小空间复杂度 $O(1)$。虽然看似有内外两层循环但 l 和 r 各自最多移动 N 次因此整体仍是线性复杂度——这正是滑动窗口相对暴力枚举 $O(N^2)$ 的优化所在。多语言实现对照仓库中 209 题题解 还提供了 JavaScript 与 C 版本便于对比同一思路在不同语言下的落地方式。JavaScript 版本借助数组模拟窗口、shift()实现左出队var minSubArrayLen function (s, nums) { if (nums.length 0) return 0; const slideWindow []; let acc 0; let min null; for (let i 0; i nums.length 1; i) { const num nums[i]; while (acc s) { if (min null || slideWindow.length min) { min slideWindow.length; } acc acc - slideWindow.shift(); } slideWindow.push(num); acc slideWindow.reduce((a, b) a b, 0); } return min || 0; };C 版本与 Python 模板同构的索引双指针写法class Solution { public: int minSubArrayLen(int s, vectorint nums) { int num_len nums.size(); int left0, right0, total0, min_len num_len1; while (right num_len) { do { total nums[right]; } while (right num_len total s); while (left right total - nums[left] s) total - nums[left]; if (total s min_len right - left) min_len right- left; } return min_len num_len ? min_len: 0; } };源码级延伸从暴力枚举推导出双指针滑动窗口为什么能把 $O(N^2)$ 优化到 $O(N)$1004. 最大连续 1 的个数 III 的题解给出了非常清晰的推导过程可以作为理解该套路正确性的核心证据。暴力枚举的思路若没有最多可以将 K 个值从 0 变成 1这个条件1004 就是一个常规的滑动窗口模板题。加上条件后暴力解法无非是枚举所有子数组$O(N^2)$再逐一判断子数组是否满足将最多 K 个 0 变成 1 后全部为 1。滑动窗口为何能省去重复计算滑动窗口可行的根本原因在于它本身就是暴力枚举的优化。例如判断完子数组 A[2:3] 后继续判断 A[2:4]只需在窗口右端新增 A[4]同时结合 A[2:3] 已有的计数信息即可。滑动窗口专门优化这种每次只在端点变化、中间不变的重复计算场景把窗口内计数信息的维护从 $O(w)$ 降到 $O(1)$w 为窗口大小。更进一步也不需要两层循环枚举所有子数组。换个角度思考所有子数组等价于以索引 0 为右端点的所有子数组 以索引 1 为右端点的所有子数组 …… 以索引 n-1 为右端点的所有子数组。这样就能用右指针模拟右端点、左指针模拟左端点。如果以索引 i 为右端点的子数组中 0 的个数不大于 k那么左指针 l 没必要右移——因为此时以任意 l ≤ i ≤ i 为左端点、i 为右端点的子数组 0 的个数都不大于 k但它们更短、不可能是答案直接右移右指针即可。由此将时间复杂度从 $O(N^2)$ 降到 $O(N)$。1004 的 Python3 实现可变窗口求最大另一种模板形态——收缩条件放在while中class Solution: def longestOnes(self, A: List[int], K: int) - int: i ans 0 for j in range(len(A)): K - A[j] 0 while K 0: K A[i] 0 i 1 ans max(ans, j - i 1) return ans代码中K - A[j] 0与K A[i] 0巧妙地利用了布尔值与整数的等价性加入 0 时 K 减一左指针移出 0 时 K 加一当 K 小于 0 说明窗口内 0 的数量超标收缩左边界。复杂度时间复杂度 $O(N)$空间复杂度 $O(1)$。题目列表滑动窗口实战题单以下题目有的信息比较直接一眼能看出用滑动窗口有的信息比较隐蔽需要自己发掘英文版文档标注为 Not Translated Yet即暂未翻译【PythonJavaScript】滑动窗口3. 无重复字符的最长子串——可变窗口求最大仓库题解见 3.longest-substring-without-repeating-characters.md最小覆盖子串——可变窗口求最小长度最小的子数组——可变窗口求最小仓库题解见 209.minimum-size-subarray-sum.md【Python】滑动窗口438. 找到字符串中所有字母异位词——固定窗口【904. 水果成篮】Python3【930. 和相同的二元子数组】JavaPython【992. K 个不同整数的子数组】滑动窗口Python最长湍流子数组——仓库题解见 978.longest-turbulent-subarray.md【1004. 最大连续 1 的个数 III】滑动窗口Python3——仓库题解见 1004.max-consecutive-ones-iii.md【1234. 替换子串得到平衡字符串】[Java/C/Python] Sliding Window【1248. 统计「优美子数组」】滑动窗口Python将 x 减到 0 的最小操作数——仓库题解见 1658.minimum-operations-to-reduce-x-to-zero.md隐蔽型题目的识别技巧题单中有两类题目值得重点体会信息隐蔽的含义978. 最长湍流子数组题解 先把相邻元素的差转换为符号数组 arr 表示正号、- 表示负号、0 表示相邻相等于是最长湍流子数组转化为正负符号相间的最长子序列这就是典型的连续问题可用滑动窗口求解。实现中注意两个细节0 始终不能出现在答案中属于需要特殊判断的临界条件判断符号是否相同用了a ^ b 0的技巧异或判断符号可避免大数相乘溢出。class Solution: def maxTurbulenceSize(self, A: List[int]) - int: ans 1 i 0 for j in range(2, len(A)): if (A[j] A[j - 1]): i j elif (A[j] - A[j - 1]) ^ (A[j - 1] - A[j - 2]) 0: i j - 1 ans max(ans, j - i 1) return ans1658. 将 x 减到 0 的最小操作数题解 展示了逆向思考这一隐蔽技巧。题目要求从数组两端移除元素使 x 减到 0正向做是难以直接套窗口的但逆向看剩余数组一定是原数组的中间连续部分于是问题转化为求和为 sum(nums) - x 的最长连续子数组用数组总长减去它就是最小操作数。这正是典型的滑动窗口问题class Solution: def minOperations(self, nums: List[int], x: int) - int: # 逆向求解滑动窗口 i 0 target sum(nums) - x win 0 ans len(nums) if target 0: return ans for j in range(len(nums)): win nums[j] while i j and win target: win - nums[i] i 1 if win target: ans min(ans, len(nums) - (j - i 1)) return -1 if ans len(nums) else ans该题题解还先演示了堆多路归并与记忆化递归两种解法并分析其复杂度劣势最终落到 $O(N)$ 的滑动窗口解法是一个很好的多解法对比、逐步优化案例时间复杂度 $O(N)$空间复杂度 $O(1)$。总结滑动窗口专题的核心结论可归纳为识别信号题面出现连续子串 / 连续子数组优先联想滑动窗口双指针三种类型固定窗口l、r 同步平移、可变窗口求最大、可变窗口求最小后两者统称可变窗口统一框架外层右指针扩展 内层左指针收缩 窗口信息增量维护 答案更新求最小窗口时在满足条件处收缩并取min求最大窗口时在满足条件处取max复杂度收益双指针各移动至多 N 次时间复杂度 $O(N)$、空间 $O(1)$相对暴力枚举 $O(N^2)$ 是质变进阶技巧识别隐蔽题目的关键是把题意翻译成连续语义如 978 的符号数组、1658 的逆向思维再套用模板。仓库内更多相关资源滑动窗口专题中文、英文版以及 README 总目录 中收录的各类算法套路文章可作为后续深入学习的索引。赞分享文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载相关推荐Voicebox快速入门5分钟创建第一个声音档案并生成AI语音Voicebox快速入门5分钟创建第一个声音档案并生成AI语音 Voicebox 是一款免费开源的 AI 语音工作室只需几秒录音就能克隆任意声音创建「声音人工智能语音音频桌面应用本地部署MCP 服务shadcn CLI 完全指南create / init / apply / add 四大命令的用法与源码解析shadcn CLI 完全指南create / init / apply / add 四大命令的用法与源码解析 本文基于 packages/shadcn/RE前端UI组件设计系统LeetCode 480 滑动窗口中位数Sliding Window Median四种解法全解析从暴力排序到双堆惰性删除LeetCode 480 滑动窗口中位数Sliding Window Median四种解法全解析从暴力排序到双堆惰性删除 导读 本文以 articles/示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考