力扣题型：滑动窗口

基本解题思想

主要有：定长窗口、变长窗口。 通常用双指针l和r对窗口定界，那么r-l+1表示窗口大小。 通过不断移动窗口，比较窗口内的元素与题目要求是否相符，来解决问题。 此类题目，往往与统计字符个数的哈希表连用，但是这种情况下，如果是求等会很方便，如果求大于/小于这种，就应该用堆了，这种时候可能效率没有滑动窗口高，比如209。

窗口的移动情况，往往有：

• 每次左右指针同时前进。【438】
• 每次右指针移动若干步进行扩张，而后左指针前进若干步进行收缩。【3】
• 每次右指针前进一步，而左指针前进若干步。【209】

字符串滑动窗口

• 438. 找到字符串中所有字母异位词（变位词）：定长滑动窗口+哈希表，先向右扩张到p串大小然后保持不变，满足条件就找到一个结果，重复这个过程直到字符串末尾。哈希表维护字符出现次数，可先将窗口大小从0变到m然后保持不变，窗口向右滑动，r对应字符数+1，l对应字符数-1，查看哈希表什么时候全为0就是满足条件的一个解。也可以使用一个变量表示当前窗口与p串相差的字符数（通过初始扫描含26个字符的哈希表得到），r对应字符数由0变1才增加，l对应字符数由1变0才减少，直到这个变量为0，时间复杂度O(m + C+ n)，空间复杂度O(C), C=26。
• 3. 无重复字符的最长子串：变长滑动窗口+哈希表，先向右扩张遇到重复则立马收缩到不重复，然后继续重复这个过程。哈希表维护当前字符，r前进时没有重复则继续，有重复则l收缩直至没有重复，时间复杂度O(n)，空间复杂度O(n)。
• 76. 最小覆盖子串：类似438，滑动窗口+哈希表+统计变量，先向右扩张到包含t，然后收缩到最小，不断重复这个过程直到找到全局最小。这次用哈希表counts存t中字符出现次数，窗口先不断扩张，便可以不断将counts中的字符数量-1，同时如果变成0那么remains-1表示有一个字符完成条件，counts中没有的字符可以忽略也可以减这个没影响，因为我们看的是统计变量remains的标志是否为0，而统计标志的增减只与t中字符有关。一旦remains为0，那么我们立即着手收缩窗口直到remains不为0，收缩的时候，counts中对应字符+1，如果变成了1，表示这个字符又不满足条件了，remains则需要+1。这样收紧窗口之后，就可以进行一次判断，看此次的窗口大小是否是最小的，如果是则记录这个窗口的信息。
• 209. 长度最小的子数组：滑动窗口+累加和，每次移动右指针，而收缩左指针。
• 713. 乘积小于K的子数组：这道题不要看官方题解，会误导人。时间复杂度O(n)：双指针滑动窗口，右指针每次前进1步，左指针每次找到符合条件的最小索引。左指针不用从头开始，因为它所处的位置是刚好满足条件的最小索引，回退只会变大。