【算法方法总结·三】滑动窗口的一些技巧和注意事项

【算法方法总结·三】滑动窗口的一些技巧和注意事项

• 【算法方法总结·一】二分法的一些技巧和注意事项
• 【算法方法总结·二】双指针的一些技巧和注意事项
• 【算法方法总结·三】滑动窗口的一些技巧和注意事项

---

【滑动窗口】

数组的和 随着 右边指针 移动一定是 非递减 的，就是 单调，不能包含负数

• 暴力解法 时间复杂度：O(n^2)
• 滑动窗口 时间复杂度：O(n)
• 数组不是单调的话，不要用 滑动窗口，考虑用 前缀和（前缀和很简单，就放此章一块讲了）
• 所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果，将O(n^2)的暴力解法降为O(n)
• 使用了双指针机制，left 和 right 指针维护窗口边界，初始均为 0，外层循环用 right 扩大窗口，内层循环用 left 缩小窗口

---

滑动窗口的使用条件

数组的和 随着 右边指针 移动一定是 非递减 的，就是 单调

• ​数据连续性：需要 数组单调 / 字符串的连续子序列问题。
• ​存在重复计算：暴力解法中存在冗余计算，窗口滑动可复用部分结果。
• ​窗口状态可维护：窗口内的状态（如字符频率、和）可通过指针移动快速更新。
• ​时间复杂度优化需求：通常将时间复杂度从 O(n²) 优化至 O(n)。

实现滑动窗口，应确定三点：

• （1）窗口内 是什么？
• （2）如何 移动 窗口的 起始位置？
• （3）如何 移动 窗口的 结束位置？

---

滑动窗口模板

//外层循环扩展右边界，内层循环扩展左边界
int l = 0;
for (int r = 0 ; r < n ; r++) {//当前考虑的元素while (l <= r && check()) {//区间[left,right]不符合题意//扩展左边界}//区间[left,right]符合题意，统计相关信息
}

---

相关力扣题

• 相关解法见【算法题解答·三】滑动窗口

3.无重复字符的最长子串

438.找到字符串中所有字母异位词

209.长度最小的子数组

---

【前缀和】

前缀和 的思想是 重复利用 计算过的 子数组之和，从而降低区间查询需要累加计算的次数

---

【滑动窗口】和【前缀和】的选择

特性

维度	滑动窗口	​前缀和
核心机制	双指针 动态调整 窗口边界	预处理 数组的累积和
数据特性	处理 连续子序列 问题	快速计算 任意区间和
操作方向​	​单向滑动（通常右指针主导）	静态存储，支持 任意区间 查询

选择策略

• 优先用滑动窗口：
  – 需要处理连续子序列的最值问题
  – 数据满足单向滑动条件​（如均为正数）

• ​优先用前缀和：
  – 需要快速计算区间和​（尤其是多次查询）
  – 数据包含负数或需要统计特定区间性质​（如奇偶性）