企业官网建设流程全解析

• 文档
• 教程
• 知识库

滑动窗口是算法题解中处理"连续子串""连续子数组"类问题的高频套路，本质上是一种双指针（two pointers）技巧，可将暴力枚举的 $O(N^2)$ 复杂度优化到 $O(N)$。本文以 leetcode 题解仓库（滑动窗口专题）为核心，完整讲解滑动窗口的三种常见类型、固定窗口与可变窗口的指针维护规则、可直接套用的代码模板，并结合仓库内 209. 长度最小的子数组、3. 无重复字符的最长子串、1004. 最大连续 1 的个数 III、978. 最长湍流子数组、1658. 将 x 减到 0 的最小操作数 等真实题解，带你建立"看到连续问题就想到滑动窗口"的条件反射，并掌握从暴力枚举出发一步步优化到 $O(N)$ 双指针解法的完整推导路径。

209. 长度最小的子数组滑动窗口过程示意图

从 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，分别表示窗口的左右顶点，并且保证：

1. l 初始化为 0
2. 初始化 r，使得 r - l + 1 等于窗口大小
3. 同时移动 l 和 r
4. 判断窗口内的连续元素是否满足题目限定的条件
   • 4.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解（返回或继续寻找更优）
   • 4.2 如果不满足，则继续寻找合适的窗口

固定窗口的特征是左右指针同步平移，窗口长度始终保持r - l + 1不变，因此关键在于每次平移后对窗口内信息的增量维护。典型的固定窗口题如 438. 找到字符串中所有字母异位词（见下方题目列表）：窗口长度固定为 p 的长度，滑动过程中只需维护字符频次计数。

可变窗口大小

对于可变窗口，同样初始化左右指针 l 和 r，分别表示窗口的左右顶点，后面有所不同，需要保证：

1. l 和 r 都初始化为 0
2. r 指针移动一步（向右扩展）
3. 判断窗口内的连续元素是否满足题目限定的条件
   • 3.1 如果满足：
     • 3.1.1 需要最优解时，尝试通过移动 l 指针缩小窗口大小，循环执行 3.1
     • 3.1.2 否则返回当前解
   • 3.2 如果不满足，则继续扩展

形象地来看，就是r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。即：先移动 r 找到一个"合适窗口"，再移动 l 去缩小窗口、逼近最优解。

可变窗口的典型代表就是求最小满足条件窗口的 209. 长度最小的子数组，以及求最大满足条件窗口的 3. 无重复字符的最长子串：

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：左指针与窗口内元素和均初始化为 0；
• ans = len(nums) + 1：初始化答案为不可能达到的较大值（N+1），用是否仍等于该值来判断是否存在合法解，这也是最后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, vector<int>& nums) { int num_len= nums.size(); int left=0, right=0, total=0, min_len= num_len+1; 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"，即暂未翻译）：

• 【Python，JavaScript】滑动窗口（3. 无重复字符的最长子串）——可变窗口求最大，仓库题解见 3.longest-substring-without-repeating-characters.md
• 76. 最小覆盖子串——可变窗口求最小
• 209. 长度最小的子数组——可变窗口求最小，仓库题解见 209.minimum-size-subarray-sum.md
• 【Python】滑动窗口（438. 找到字符串中所有字母异位词）——固定窗口
• 【904. 水果成篮】（Python3）
• 【930. 和相同的二元子数组】（Java，Python）
• 【992. K 个不同整数的子数组】滑动窗口（Python）
• 978. 最长湍流子数组——仓库题解见 978.longest-turbulent-subarray.md
• 【1004. 最大连续 1 的个数 III】滑动窗口（Python3）——仓库题解见 1004.max-consecutive-ones-iii.md
• 【1234. 替换子串得到平衡字符串】[Java/C++/Python] Sliding Window
• 【1248. 统计「优美子数组」】滑动窗口（Python）
• 1658. 将 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 ans

1658. 将 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)$。

总结

滑动窗口专题的核心结论可归纳为：

1. 识别信号：题面出现"连续子串 / 连续子数组"，优先联想滑动窗口（双指针）；
2. 三种类型：固定窗口（l、r 同步平移）、可变窗口求最大、可变窗口求最小，后两者统称可变窗口；
3. 统一框架：外层右指针扩展 + 内层左指针收缩 + 窗口信息增量维护 + 答案更新；求最小窗口时在满足条件处收缩并取min，求最大窗口时在满足条件处取max；
4. 复杂度收益：双指针各移动至多 N 次，时间复杂度 $O(N)$、空间 $O(1)$，相对暴力枚举 $O(N^2)$ 是质变；
5. 进阶技巧：识别隐蔽题目的关键是把题意翻译成"连续"语义（如 978 的符号数组、1658 的逆向思维），再套用模板。

仓库内更多相关资源：滑动窗口专题（中文）、英文版，以及 README 总目录 中收录的各类算法套路文章，可作为后续深入学习的索引。

• 文档
• 教程
• 知识库