滑动窗口算法：高效解决子区间问题的双指针技巧

1. 滑动窗口算法核心思想解析

滑动窗口（Sliding Window）是解决数组/字符串子区间问题的高效算法范式。它的核心在于维护一个动态变化的窗口，通过调整窗口边界来寻找满足条件的解，避免了暴力枚举带来的高时间复杂度。

1.1 算法适用场景特征

适合滑动窗口解决的问题通常具备以下三个特征：

1. 数据结构为线性序列（数组、字符串、链表等）
2. 求解目标与子区间相关（如最长/最短满足条件的子串）
3. 窗口内元素满足某种单调性（如元素和随窗口增大而单调递增）

典型应用场景包括：

• 无重复字符的最长子串（LeetCode 3）
• 最小覆盖子串（LeetCode 76）
• 字符串排列（LeetCode 567）
• 最大连续1的个数（LeetCode 487）

1.2 双指针实现原理

滑动窗口通常用双指针实现，分为固定窗口和可变窗口两种模式：

// 可变窗口模板 int left = 0, right = 0; while (right < s.size()) { // 扩展右边界 window.add(s[right]); right++; // 满足条件时收缩左边界 while (valid(window)) { // 更新结果 res = update(res, window); window.remove(s[left]); left++; } }

固定窗口则是维护一个长度不变的窗口，典型如求长度为k的子数组最大和：

// 固定窗口模板 int sum = 0, maxSum = INT_MIN; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; if (i >= k - 1) { maxSum = max(maxSum, sum); sum -= nums[i - (k - 1)]; } }

2. LeetCode Hot 100滑动窗口经典题解

2.1 无重复字符的最长子串（LeetCode 3）

问题描述：给定字符串s，找出不含有重复字符的最长子串长度。

int lengthOfLongestSubstring(string s) { unordered_map<char, int> window; int left = 0, right = 0; int res = 0; while (right < s.size()) { char c = s[right]; right++; window[c]++; while (window[c] > 1) { char d = s[left]; left++; window[d]--; } res = max(res, right - left); } return res; }

关键点：

1. 使用哈希表记录窗口内字符出现次数
2. 当某个字符计数>1时收缩左边界
3. 每次窗口合法时更新最大长度

时间复杂度：O(n)，空间复杂度：O(字符集大小)

2.2 最小覆盖子串（LeetCode 76）

问题描述：给定字符串s和t，在s中找出包含t所有字符的最短子串。

string minWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 0; int start = 0, len = INT_MAX; while (right < s.size()) { char c = s[right]; right++; if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } while (valid == need.size()) { if (right - left < len) { start = left; len = right - left; } char d = s[left]; left++; if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } return len == INT_MAX ? "" : s.substr(start, len); }

关键点：

1. 使用两个哈希表分别记录需要的字符和当前窗口的字符
2. valid变量统计满足条件的字符个数
3. 当valid等于need大小时尝试收缩窗口

时间复杂度：O(n)，空间复杂度：O(字符集大小)

3. 滑动窗口的优化技巧

3.1 哈希表替代方案

对于字符集有限的问题（如仅小写字母），可以用数组代替哈希表提升效率：

int window[26] = {0}; // 小写字母频率统计

3.2 边界条件处理

常见边界陷阱：

1. 空字符串输入
2. 目标子串不存在的情况
3. 所有字符都相同的情况

3.3 复杂度的数学证明

滑动窗口的O(n)时间复杂度可以通过摊还分析证明：

• 每个元素最多被右指针访问一次
• 每个元素最多被左指针访问一次
• 总操作次数为2n，因此是线性复杂度

4. 滑动窗口与其他算法的比较

4.1 与暴力法的对比

暴力解法通常需要O(n^2)时间复杂度：

// 暴力解法示例 for (int i = 0; i < n; i++) for (int j = i; j < n; j++) if (isValid(i, j)) updateResult();

滑动窗口通过消除重复计算将复杂度降至O(n)

4.2 与动态规划的关系

某些滑动窗口问题可以用DP解决，但空间复杂度更高：

• 滑动窗口：O(1)或O(m)额外空间
• DP解法：通常需要O(n)空间

4.3 与双指针的区别

广义上滑动窗口属于双指针技术，但更强调：

1. 明确的窗口概念
2. 窗口内元素的统计信息维护
3. 特定的收缩/扩展条件

5. 实战问题分类解析

5.1 计数类问题

特征：需要统计窗口内某类元素的数量

例题：最大连续1的个数III（LeetCode 1004）

int longestOnes(vector<int>& nums, int k) { int left = 0, right = 0; int zeros = 0; int res = 0; while (right < nums.size()) { if (nums[right] == 0) zeros++; right++; while (zeros > k) { if (nums[left] == 0) zeros--; left++; } res = max(res, right - left); } return res; }

5.2 子串排列问题

特征：判断某排列是否存在于字符串中

例题：字符串的排列（LeetCode 567）

bool checkInclusion(string s1, string s2) { unordered_map<char, int> need, window; for (char c : s1) need[c]++; int left = 0, right = 0; int valid = 0; while (right < s2.size()) { char c = s2[right]; right++; if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } while (right - left >= s1.size()) { if (valid == need.size()) return true; char d = s2[left]; left++; if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } return false; }

5.3 最优解问题

特征：寻找满足条件的最优（最大/最小）子区间

例题：乘积小于K的子数组（LeetCode 713）

int numSubarrayProductLessThanK(vector<int>& nums, int k) { if (k <= 1) return 0; int left = 0, right = 0; int product = 1; int res = 0; while (right < nums.size()) { product *= nums[right]; right++; while (product >= k) { product /= nums[left]; left++; } res += right - left; } return res; }

6. 滑动窗口的常见陷阱与调试技巧

6.1 窗口收缩条件错误

典型错误：

1. 收缩过早导致错过最优解
2. 收缩不足导致结果不准确

调试方法：

• 打印窗口左右边界和关键变量
• 用小规模测试用例手动模拟

6.2 哈希表更新时机不当

常见错误：

1. 先更新结果再收缩窗口
2. 哈希表更新与指针移动不同步

正确做法：

// 正确的更新顺序 window.add(s[right]); right++; // 检查条件 while (invalid(window)) { window.remove(s[left]); left++; } // 更新结果 update(res);

6.3 特殊输入处理

需要特别注意：

1. 空输入
2. 所有元素相同
3. 极值情况（如k=0或k>n）

7. 滑动窗口在竞赛中的应用

7.1 多指针扩展

某些问题需要维护多个窗口或使用多指针：

• 三指针解决某些特殊子序列问题
• 并行滑动多个窗口处理复杂条件

7.2 与单调结构结合

滑动窗口常与单调队列/栈结合解决更复杂问题：

• 滑动窗口最大值（LeetCode 239）
• 满足条件的子数组个数（LeetCode 795）

7.3 非典型滑动窗口

一些变种问题需要灵活应用窗口思想：

• 窗口大小不固定但受其他条件约束
• 窗口性质需要复杂数据结构维护

8. 性能优化进阶技巧

8.1 位运算优化

对于特定问题可以用位掩码代替哈希表：

int window = 0; // 用位表示字符出现情况 window |= (1 << (c - 'a')); // 设置位

8.2 预处理加速

提前计算前缀和等辅助数组：

vector<int> prefix(n + 1, 0); for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];

8.3 并行计算

对于超大数组可以考虑：

1. 分段处理
2. 多线程滑动不同区段
3. 合并部分结果

9. 滑动窗口的数学本质

从数学角度看，滑动窗口技术实际上是：

1. 在解空间中的一种剪枝策略
2. 利用单调性减少不必要的计算
3. 对暴力解法的优化重构

其正确性依赖于问题的两个性质：

1. 窗口的可行性（窗口收缩时可以确保不遗漏解）
2. 解的最优子结构（局部最优能导向全局最优）

10. 扩展学习建议

10.1 推荐练习题单

按难度排序的滑动窗口练习题：

1. 长度最小的子数组（LeetCode 209）
2. 替换后的最长重复字符（LeetCode 424）
3. 最多包含两个不同字符的最长子串（LeetCode 159）
4. 滑动窗口最大值（LeetCode 239）
5. 最小窗口子序列（LeetCode 727）

10.2 相关算法领域

滑动窗口与以下算法密切相关：

1. 双指针技术
2. 尺取法（竞赛常用）
3. 贪心算法
4. 字符串匹配算法（如KMP）

10.3 实际工程应用

滑动窗口在工程中的典型应用：

1. 网络流量控制（TCP滑动窗口）
2. 实时数据处理（如计算移动平均）
3. 日志分析（检测异常模式）
4. 股票分析（计算技术指标）