1296 字
6 分钟
滑动窗口：子数组/子串问题的通用解法
概述
滑动窗口（Sliding Window） 是双指针在连续区间问题中的常见形式。它维护一个窗口 [left, right] 或 [left, right)，随着右指针扩张、左指针收缩，在 O(n) 时间内处理子数组或子串问题。
前置知识
- 双指针：窗口左右边界由两个指针维护
- 哈希表 / 计数器：记录窗口内字符或元素状态
- 区间不变量：明确窗口当前满足或不满足什么条件
问题定义
给定数组或字符串，寻找满足某种条件的连续区间，例如最大长度、最小长度、固定长度最优值或覆盖关系。
| 要素 | 说明 |
|---|---|
| 输入 | 数组、字符串、目标长度或约束条件 |
| 输出 | 最长/最短窗口长度、窗口内容或统计值 |
| 核心状态 | left、right、窗口计数、当前答案 |
| 常见类型 | 定长窗口、变长窗口、覆盖窗口 |
核心原理：分步图解
以变长窗口为例，右指针负责扩张，左指针负责恢复条件：
s: a b c a b c b bindex: 0 1 2 3 4 5 6 7window: [left ...... right]graph LR
A[右指针加入元素] --> B[更新窗口状态]
B --> C{窗口是否合法?}
C -->|否| D[左指针收缩]
D --> B
C -->|是| E[更新答案]滑动窗口之所以是 O(n)，是因为每个元素最多被右指针加入一次、被左指针移出一次。
算法精细步骤
算法：VariableSlidingWindow(nums)输入：数组或字符串 nums输出：满足条件的最优窗口
1. left ← 02. 初始化窗口状态 window3. for right from 0 to nums.length - 1:4. 将 nums[right] 加入 window5. while window 不满足约束：6. 将 nums[left] 移出 window7. left ← left + 18. 用当前窗口更新答案9. 返回答案复杂度分析：
| 窗口类型 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 定长窗口 | O(n) | O(1) | 每次进一个、出一个 |
| 变长窗口 | O(n) | O(k) | k 为窗口内不同元素数 |
| 覆盖窗口 | O(n) | O(字符集大小) | 需要维护 need/window 计数 |
| 暴力枚举 | O(n²) 或更高 | O(1) | 枚举所有连续区间 |
TypeScript 实现
1. 定长窗口最大和
function maxSumSubarray(nums: number[], k: number): number { let sum = 0;
for (let i = 0; i < k; i++) { sum += nums[i]; }
let best = sum; for (let right = k; right < nums.length; right++) { sum += nums[right] - nums[right - k]; best = Math.max(best, sum); }
return best;}2. 最大平均数
function findMaxAverage(nums: number[], k: number): number { return maxSumSubarray(nums, k) / k;}3. 无重复字符的最长子串
function lengthOfLongestSubstring(s: string): number { const window = new Map<string, number>(); let left = 0; let best = 0;
for (let right = 0; right < s.length; right++) { const char = s[right]; window.set(char, (window.get(char) ?? 0) + 1);
while (window.get(char)! > 1) { const removed = s[left]; window.set(removed, window.get(removed)! - 1); left++; }
best = Math.max(best, right - left + 1); }
return best;}4. 长度最小的子数组
function minSubArrayLen(target: number, nums: number[]): number { let left = 0; let sum = 0; let best = Infinity;
for (let right = 0; right < nums.length; right++) { sum += nums[right];
while (sum >= target) { best = Math.min(best, right - left + 1); sum -= nums[left]; left++; } }
return best === Infinity ? 0 : best;}5. 最小覆盖子串
function minWindow(s: string, t: string): string { const need = new Map<string, number>(); const window = new Map<string, number>();
for (const char of t) { need.set(char, (need.get(char) ?? 0) + 1); }
let left = 0; let valid = 0; let start = 0; let minLength = Infinity;
for (let right = 0; right < s.length; right++) { const char = s[right]; if (need.has(char)) { window.set(char, (window.get(char) ?? 0) + 1); if (window.get(char) === need.get(char)) valid++; }
while (valid === need.size) { if (right - left + 1 < minLength) { start = left; minLength = right - left + 1; }
const removed = s[left]; left++;
if (need.has(removed)) { if (window.get(removed) === need.get(removed)) valid--; window.set(removed, window.get(removed)! - 1); } } }
return minLength === Infinity ? '' : s.slice(start, start + minLength);}工程优化：窗口状态要可增量维护
滑动窗口的前提是窗口变化时，状态可以快速更新。
| 状态 | 入窗口 | 出窗口 | 适用问题 |
|---|---|---|---|
| 求和 | sum += x | sum -= x | 子数组和、平均值 |
| 计数 | count[x]++ | count[x]-- | 字符覆盖、频率限制 |
| 去重 | 记录出现次数 | 重复时收缩 | 无重复子串 |
| 最大/最小 | 单调队列 | 过期元素出队 | 窗口最大值 |
如果窗口状态不能 O(1) 或均摊 O(1) 更新，滑动窗口可能退化，需考虑单调队列、堆或其他结构。
应用与局限
典型应用
- 子数组/子串最长或最短问题
- 固定长度窗口统计
- 字符串覆盖、异位词、重复字符限制
- 流式数据最近一段统计
局限性
| 局限 | 说明 |
|---|---|
| 必须是连续区间 | 非连续子序列不适用 |
| 条件需可维护 | 窗口扩张/收缩后要能快速更新状态 |
| 单调性要求 | 变长窗口通常依赖“收缩会改善约束” |
总结
graph LR
A[定义窗口含义] --> B[右指针扩张]
B --> C[更新窗口状态]
C --> D[左指针收缩]
D --> E[更新答案]核心要点：
- 滑动窗口适合连续子数组和子串问题。
- 定长窗口关注进出平衡，变长窗口关注合法性维护。
- 每个元素最多进出窗口一次，所以通常是 O(n)。
- 写代码前先定义窗口状态和收缩条件。
滑动窗口：子数组/子串问题的通用解法
https://www.hehonglei.cn/technology/sliding-window/