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

  • 【算法方法总结·一】二分法的一些技巧和注意事项
  • 【算法方法总结·二】双指针的一些技巧和注意事项
  • 【算法方法总结·三】滑动窗口的一些技巧和注意事项 🎯
  • 【算法方法总结·四】字符串操作的一些技巧和注意事项
  • 【算法方法总结·五】链表操作的一些技巧和注意事项
  • 【算法方法总结·六】栈队列堆的一些技巧和注意事项

【滑动窗口】

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

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

滑动窗口的使用条件

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

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

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

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

滑动窗口模板

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

相关力扣题

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

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

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

209.长度最小的子数组

【前缀和】

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

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

特性

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

选择策略

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

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