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

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

【滑动窗口】

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

暴力解法 时间复杂度：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]符合题意，统计相关信息
}

【前缀和】

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

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

特性

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