Leetcode刷题之滑动窗口
双指针类型题目，持续更新
邓宁-克鲁格效应是指的是能力欠缺的人在自己欠考虑的决定的基础上得出错误结论，但是无法正确认识到自身的不足，辨别错误行为，是一种认知偏差现象。这些能力欠缺者们沉浸在自我营造的虚幻的优势之中，常常高估自己的能力水平，却无法客观评价他人的能力。
什么是「滑动窗口算法」（sliding window algorithm），有哪些应用场景？ - 知乎
最高赞的回答不错。滑动窗口在处理数组和字符串上很适用。
窗口大小分为固定的和可变的两种。
固定的滑动窗口：后面加进来一个，前面推出去一个。
可变的滑动窗口：窗口加到到满足条件或不满足条件为止，前面的元素推出去。
【详细图解】滑动窗口（超99） - 最短超串 - 力扣（LeetCode）
可用于查找满足某些条件的连续区间的性质（如长度）。由于区间连续，当区间变化时，可以通过之前的计算结果来对搜索空间进行剪枝。
简单
219. 存在重复元素 II
维护一个可变的滑动窗（用Set）
643. 子数组最大平均数 I
两种方法。1. presum，前缀和。2. 滑动窗
presum：创建一个数组，长度为N。第i个元素存放前i个元素之和（注意自己的代码写的是否包括了第i个元素）。
滑动窗：先取得前k个元素和，形成一个长度为k的窗口。然后开始移动，每向后移动一个元素，加上当前元素，减去第一个元素。
中等
187. 重复的DNA序列
一般的滑动窗感觉占用空间太大了，即用哈希表，子串映射到出现次数。但是对于最大长度为$10^5$的字符串，我觉得太大。（但是还是可以用的，面试的时候想不出更好的就用这个！做出来比做好可能更重要！）
这里第一次学习到了字符串哈希。
记录一下为什么用131313：字符串哈希本身存在哈希冲突的可能，一般会在尝试 131之后尝试使用 13131，然后再尝试使用比 13131 更大的质数。（参考三叶的答案）
209. 长度最小的子数组 ☆
没有理清楚，记录一下自己的代码。
滑动窗口的经典题目。
还有其他方法，比如前缀和。
220. 存在重复元素 III
暴力解法即遍历元素，对第i个元素向后检查k个元素，但是这样做会超时。
三叶姐的题解展示了两种方法：
滑动窗&红黑树
对暴力解法进行优化，可以对检查k个元素的过程进行优化。k个元素用一个有序集合来维护，而这个集合需要实现高效的查询和插入删除操作。由此可以想到使用树。
再利用TreeMap中的ceiling和flooring函数，得到最接近当前元素的值。
AVL：一种平衡二叉搜索树。具有两个性质：左边大于右边；任意节点的孩子节点之间高度差最大为1。因为第二个性质，在插入或删除元素时可能需要进行重平衡，可以通过旋转的方法实现。一次平衡操作伴随着多次旋转。
RBT：红黑树。是一种二叉树，但每一个节点多了一个属性：颜色。是一种弱平衡二叉搜索树，它不像AVL要求左右高度差不大于1，但对路径长度要求“任何一条路径的长度不能大于其他路径长度的两倍”。这样使得RBT比AVL在插删操作上，运行速度更快，因为旋转次数变少。
BST：二叉搜索树（binary search tree）
桶
桶排序
令需要排序的序列一共有n个元素，将这n个元素分到m个桶中，这些桶满足：当前桶中的元素都小于后面桶的元素。然后对每个桶分别进行排序，最后合并每个桶的结果。当m接近于n时，时间复杂度趋近于
O(n)。桶排序是一种空间换时间的方法，它要求序列分布尽可能均匀，否则会出现空间上的浪费。顺便再介绍一下计数排序和基数排序，他们和桶排序都是线性时间复杂度的排序算法。他们是非基于比较的排序方法，基于比较的排序方法难以突破
O(nlogn)的时间复杂度。计数排序
一种特殊的桶排序。令序列的最小值为min，最大值为max，创建一个大小为max-min+1的数组。这个数组用来记录每一个数出现的次数。他是一种稳定的排序算法。
基数排序
基于多个关键字的排序。网络上对基数排序的例子以数位为主。
从首要关键字开始的排序成为MSD（Most Significant Dight），先根据首要关键字分成一些堆（如百位数），再对每个堆分别进行排序，然后串联这些堆。
从最低有效关键字开始排序，称为**LSD(Least Significant Dight)**。先按照次要关键字来排序，然后按按照首要关键字排序，不需要对每一个堆进行排序，比MSD的开销小。
注意：排序需要稳定的算法，可以用计数排序实现。稳定的排序才可以保留上一次排序的结果。
Tips：
- 以上三种方法虽然灵活性不如快排等方法，但在某些情况下，可以充分利用序列的一些性质，从而取得较好的算法性能。
424. 替换后的最长重复字符 ☆
滑动窗口的经典题
找到一个序列，使得这个序列的长度小于等于出现次数最多的字符数+k。于是问题来到了怎么确定序列中出现最多的字符数：每次右指针向右移动时，当前字符的出现次数+1，比较当前字符数与最多字符数即可。
注意在当前字符数减小时，不需要改变出现最多的字符数，它确定了滑动窗的大小，更新的滑动窗大小不应该变小。只需要在变大的时候更新。
438. 找到字符串中所有字母异位词
一个滑动窗，窗口内的元素要满足：1. 窗口内的元素出现在p中；2. 窗口内出现元素的次数要小于等于s中出现的次数。从而，当窗口大小与p长度相等时，将索引加入结果中。将这两个条件可以进行合并：窗口内元素的出现次数小于等于s中出现的次数（p中没有的字符出现次数就是0）。
这样的条件合并就需要统计所有26个字母出现的次数。我一开始的做法用map只统计p中出现了的元素，这样在还原的时候，稍微复杂了一些，不然可以合并。
滑动窗的设计思路和基本框架一致：1. 设置左右指针；2. 更新右指针引起的状态变化；3. 检查是否还满足条件，不满足条件的话左指针右移；4. 右指针右移
参考：找到字符串中所有字母异位词，滑动窗口 + 数组/双指针
题解下最赞评论：滑动窗方法能从暴力解法出发进行优化。
（PS. 我发现其实很多方法都可以通过暴力解法来出发思考）
567. 字符串的排列
和438类似。
需要注意的是子串是连续的！
（所以用字符串排列然后找是不是包含子串的方法行不通/doge）
904. 水果成篮
翻译一下题目：找到一个连续序列，这个序列中出现的数字最多为两种，求这个连续序列的最大长度。
这样一来就是滑动窗的基础用法了~
困难
76. 最小覆盖子串
蔚来笔试第三题的原题，当时滑动窗口思路没问题，但是磕了很久没做出来，今天正好做到原题，还是题做的不够多啊！
当时自己做的时候，大概方法、应该用什么来保存状态（字典和字符数）都没问题。但是在思路上还是不太对。复盘一下，当时卡壳的地方：
1.** 左指针什么时候开始移动？当时我的思路是遇到不需要的字符，而且还没遇到需要的字符时，左右指针一起移动，为了可以减少不必要的判断。
2. 左指针移动到哪里结束？这应该是当时主要卡住的地方了。滑动窗口中，右指针负责移动到满足条件为止，左指针负责找下一次搜索的起点。一点思考：尽量不要两个指针一起动**会比较容易维护，也比较清晰。
3. 状态的记录，对不要的字符要怎么处理？这里也没有想好，当时想维护一个只有需要字符的字典，这样的话如果窗口里某个需要的字符数量多出来了，又不知道该怎么处理。这道题给了一个思路，照常加减，负数的字符就代表不需要了。这点以后也可以用一用~
480. 滑动窗口中位数
见数据结构篇
992. K 个不同整数的子数组
如果理解了做法，就比较好做了。
重点：K个不同整数的子数组=最多K个整数的子数组-最多K-1个整数的子数组
然后只要写出求最多K个整数的子数组的函数即可。
滑动窗的基本操作。要注意的是求子数组的时候，每次固定右端点计算能得到的子数组，是right-left+1个。