怎样把网站的背景图片大数据智能营销
【算法方法总结·三】滑动窗口的一些技巧和注意事项
- 【算法方法总结·一】二分法的一些技巧和注意事项
- 【算法方法总结·二】双指针的一些技巧和注意事项
- 【算法方法总结·三】滑动窗口的一些技巧和注意事项
【滑动窗口】
数组的和 随着 右边指针 移动一定是 非递减 的，就是 单调，不能包含负数
- 暴力解法 时间复杂度：
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.长度最小的子数组
【前缀和】
前缀和 的思想是 重复利用 计算过的 子数组之和，从而降低区间查询需要累加计算的次数
【滑动窗口】和【前缀和】的选择
特性
| 维度 | 滑动窗口 | 前缀和 |
|---|---|---|
| 核心机制 | 双指针 动态调整 窗口边界 | 预处理 数组的累积和 |
| 数据特性 | 处理 连续子序列 问题 | 快速计算 任意区间和 |
| 操作方向 | 单向滑动（通常右指针主导） | 静态存储，支持 任意区间 查询 |
选择策略
-
优先用滑动窗口：
– 需要处理连续子序列的最值问题
– 数据满足单向滑动条件（如均为正数） -
优先用前缀和：
– 需要快速计算区间和（尤其是多次查询）
– 数据包含负数或需要统计特定区间性质（如奇偶性）