刷题总结——滑动窗口与双指针
总结
问题类型
- 滑动窗口（同向双指针）
- 定长
- 不定长
- 求最长/最大
- 求最短/最小
- 求子数组个数
- 单序列双指针（同向/相向）
- 同向：快排求partition的Lomuto算法
- 相向：快排求partition的Hoare算法、三数之和（保证有序）注意去重
- 双序列双指针
- 双指针
- 子序列判断
- 多指针
- 荷兰旗low mid high 0 0 n初始化直到mid与high相遇
思考
- 找到对应的循环不变量，在滑动窗口中通常是滑动窗口和之外区间的关系。
- 注意循环不变量引起的开闭区间关系
- “枚举右 选择左”原则
- 有的时候要先排序，之后才会发现双指针关系
- hash和计数规则的使用
滑动窗口
滑动窗口是一种同向的双指针。双指针的使用是一个for循环对指针right进行遍历，当指针right与指针left构成的窗口或者首尾两个元素满足某条件，就可以移动left指针，同时进行计数。
滑动窗口找一个符合某些性质的最长子串/连续子数组，因为left和right构成的范围必然是连续的。
定长滑动窗口
模版
- 入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
- 更新：更新答案。一般是更新最大值/最小值。
- 出：下标为 i−k+1 的元素离开窗口，更新相关统计量
不定长滑动窗口
求最大
其实就是r向右移动的时候扩大了范围，可能导致不满足约束条件，为此需要缩减左边的l。（不得不缩减，才移动左指针）
缩减l的while循环比较灵活，需要根据情况进行判断，如：
- 允许k次操作来改变cnt
- 计算首尾的差值，数学性质
- …
其实就是计数方式需要灵活使用hash或者map或者cnt数组去存储。例如LC水果成篮，美丽度等问题
求最小
尽可能缩减，使得[l，r]范围数据尽量小一些。
注意学习76题最小覆盖子串中的优化方式：为了避免每次去判断52个字母的覆盖循环，可以使用一个额外的变量表示现有子串中字母出现次数小于reference中出现次数的数目，之后：
- 遍历时，一旦次数达到要求less—
- less=0说明满足了匹配情况，可以进一步判断子串是否为最短
- 移动左侧的时候，一旦计数导致次数再次小于reference了，就less++
求子数组个数
两大类：
- 越长越合法:
ans += left - 越短越合法:
ans += right - left + 1
即每次循环枚举右维护左的时候，右端点固定，构成有效子数组的左端点在[0, left-1]区间中（越长越合法）或者[left, right]区间（越短越合法）
注意判定的时候，一定要有一个数据结构储存滑窗中的数据，可能是单变量、hash数组，也可能是map，因为有的时候只有计数到0才会进行删除
单序列双指针
相向
- 三数之和，注意对重复的判定/最接近的三数之和(思路与上述求子数组个数一样)
- 有效三角形
- 接雨水
同向
- 最短无序连续子数组(两指针相向移动，再回撤得到结果)
删除/交换元素
双指针遍历过程中交换/处理数据，考虑使用快排partition中的两种思想：
- Lomuto partition: 使用同向双指针
- Hoare partition: 使用相向双指针
双序列双指针
参考
- https://leetcode.cn/circle/discuss/0viNMK/
- https://leetcode.cn/problem-list/xb9lfcwi/
- https://leetcode.cn/problems/sort-array-by-parity/solutions/2965892/kuai-pai-partitionying-yong-shuang-zhi-z-cjyn