sliding-window
概述
滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j]（左闭，右闭合）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。
例如，我们将 [i, j] 向右滑动 1 个元素，则它将变为 [i+1, j+1]（左闭，右闭合）
这就是滑动窗口最重点的地方, 就是窗口是左闭右闭的:
- 这样 left 永远是移出区间的操作, 并且 end 大于等于 nums.length 就是退出循环的条件
- right 永远是加入区间的操作
left <= right && right < nums.length
区间的操作可以直接 while 循环, 直到区间达到要操作的阈值, 而不是 for 循环一个个处理, 增加模拟的负担
76 左右都是闭合的也可以, 最重要的是定好不要变了
Solution Tips
- 我们先不断地增加 right 指针扩大窗口
[left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符） - 此时，我们停止增加 right，转而不断增加 left 指针缩小窗口
[left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果 - 重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头
while (left <= right && right < len) {
while(right... && right < len) {
// expand window
// ... do something
right++;
}
while (left... && left <= right) {
// narrow window
// do something
left++;
}
}
很多题解, right 是一个 for 循环, 在循环内有时候是 right ++ 有时候是 left++, 脑补 debug 不好处理. 我觉得不如 right++ 到不能加, left++ 到不能加, 这样更好理解. 脑补 debug 更方便
关键词
子串, 子数组, 连续的 sub
长度固定为 k 的子数组 或者是 子数组有固定的限制条件的 f(sub) = constant; 可以考虑滑动窗口
窗口长度
窗口长度是固定
窗口长度是动态
根据题意伸缩, 固定的是窗口的某种特征, f(window) = const
最小窗口
如果要求的是最小窗口
那么可以使用固定窗口法, 从最小的窗口大小开始寻找是否存在符合题意的解, 找到了即可返回, 复杂度 O(n^2)
去头去尾留中间
方案一: 反向思维
每次去除头部、尾部, 反过来就是不断的缩小中间, 这就是正统滑动窗口的题目了
| File | solution tips overview |
|---|---|
| 2516. 每种字符至少取 K 个 | 2516. 每种字符至少取 K 个#solution tips |
| 1658. 将 x 减到 0 的最小操作数 | 1658. 将 x 减到 0 的最小操作数#solution tips |
方案二: 两个窗口
如果反向思维不好操作, 也可以选择前缀和后缀, 维护 2 个窗口
或者是前缀和后缀维护在一个窗口内
维护窗口的数据结构
找到维护窗口的合理数据结构, 是解题的关键
单纯的变量: 常见的 sum, 减去一个, 加上一个
自平衡二叉树：插入、删除、搜索都是 O(log k)
哈希表：插入、删除、搜索都是常数级
数组：插入和删除是线性的，搜索也是线性的, 数组其实也是哈希表的一种形态
不是连续的结构就可以考虑使用哈希表存储数据
哈希 Map
即需要存储每种元素的个数, 也需要统计整个 map 的大小
如果使用数组的话, 可以方便的统计元素, 但是统计集合大小的时候不方便删除, 得 indexOf + splice 执行删除
如果使用 object map, 也是可以很方便的统计元素, 也可以方便的删除, 但是无法方便的统计集合的大小
所以使用 map 是最优解.
904. 水果成篮: 需要统计每种水果的个数, 最多只能装 2 种水果
哈希 Object + MatchSize
哈希 obj 可以很方便的添加和删除, 但是无法方便的统计集合的大小, 所以额外增加一个变量用来统计集合的大小即可.
参考 76. 最小覆盖子串, 这里比使用哈希 map 更合适, 因为需要保证两个 map 完全 match, 单独使用 match 变量就可以直接知道了
438 的抵消和恢复, 没有 76 的 match 好理解, 时间复杂度是一样的