滑动窗口¶

约 3395 个字 15 行代码 1 张图片预计阅读时间 12 分钟

Reference¶

https://leetcode.cn/discuss/post/3578981/ti-dan-hua-dong-chuang-kou-ding-chang-bu-rzz7/

滑动窗口关键词：子串（子串在原字符串里的位置是连续不间断的，并且保持原有的字符顺序）、子数组（子数组在原数组里的位置是连续的，并且保持原有的元素顺序）

定长滑动窗口¶

核心思想¶

我们要计算所有长度恰好为 k 的子串中，最多可以包含多少个元音字母.

暴力枚举所有子串？时间复杂度是 \(O(nk)\)，太慢了. 能否 \(O(1)\) 计算子串的元音个数？

这是可以做到的，对于下图的字符串 abci，假如我们已经计算出了子串 abc 的元音个数，那么从子串 abc 到子串 bci，只需要考虑移除（离开窗口）的字母 a 是不是元音，以及添加（进入窗口）的字母 i 是不是元音即可，因为中间的字母 b 和 c 都在这两个子串中.

alt text

举例¶

示例 1，\(s =\) abciiiidef, \(k = 3\).

从左到右遍历 \(s\).
首先统计前 \(k - 1 = 2\) 个字母的元音个数，这有 \(1\) 个.
\(s[2] =\) c 进入窗口，此时找到了第一个长为 \(k\) 的子串 abc，现在元音个数有 \(1\) 个，更新答案最大值. 然后 \(s[0] =\) a 离开窗口，现在元音个数有 \(0\) 个.
\(s[3] =\) i 进入窗口，此时找到了第二个长为 \(k\) 的子串 bci，现在元音个数有 \(1\) 个，更新答案最大值. 然后 \(s[1] =\) b 离开窗口，现在元音个数有 \(1\) 个.
\(s[4] =\) i 进入窗口，此时找到了第三个长为 \(k\) 的子串 cii，现在元音个数有 \(2\) 个，更新答案最大值. 然后 \(s[2] =\) c 离开窗口，现在元音个数有 \(2\) 个.
\(s[5] =\) i 进入窗口，此时找到了第四个长为 \(k\) 的子串 iii，现在元音个数有 \(3\) 个，更新答案最大值. 然后 \(s[3] =\) i 离开窗口，现在元音个数有 \(2\) 个.
\(s[6] =\) d 进入窗口，此时找到了第五个长为 \(k\) 的子串 iid，现在元音个数有 \(2\) 个，更新答案最大值. 然后 \(s[4] =\) i 离开窗口，现在元音个数有 \(1\) 个.
\(s[7] =\) e 进入窗口，此时找到了第六个长为 \(k\) 的子串 ide，现在元音个数有 \(2\) 个，更新答案最大值. 然后 \(s[5] =\) i 离开窗口，现在元音个数有 \(1\) 个.
\(s[8] =\) f 进入窗口，此时找到了第七个长为 \(k\) 的子串 def，现在元音个数有 \(1\) 个，更新答案最大值. 遍历结束.

定长滑窗套路¶

我总结成三步：入-更新-出.

入：下标为 \(i\) 的元素进入窗口，更新相关统计量. 如果 \(i < k - 1\) 则重复第一步.
更新：更新答案. 一般是更新最大值/最小值.
出：下标为 \(i - k + 1\) 的元素离开窗口，更新相关统计量.

以上三步适用于所有定长滑窗题目.

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans = vowel = 0
        for i, c in enumerate(s):
            # 1. 进入窗口
            if c in "aeiou":
                vowel += 1
            if i < k - 1:  # 窗口大小不足 k
                continue
            # 2. 更新答案
            ans = max(ans, vowel)
            # 3. 离开窗口
            if s[i - k + 1] in "aeiou":
                vowel -= 1
        return ans

复杂度分析¶

时间复杂度：\(O(n)\)，其中 \(n\) 是 \(s\) 的长度.
空间复杂度：\(O(1)\). 仅用到若干额外变量.

定长滑窗中，初始化的长度为k-1，只有在更新的时候长度为k，只有这样才能保证先入再更新虽然代码没有写一个滑窗数组，但是从入-更新-出这个步骤就隐含着滑窗操作如果要求滑窗内的元素不重复，那么还需要维护一个哈希表，在入元素和出元素时对哈希表进行更新

给你字符串 s 和整数 k . 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数. 英文中的元音字母为（a, e, i, o, u）. LC1456定长子串中元音的最大数目 [x]
- 初始化滑窗 [0,k-2]（长度为k-1）计算元音字母数c
- 从左往右 i入，如果i对应为元音字母，c+=1，与最大值比并更新最大值，再看i-k+1，如果i-k+1对应为元音字母，c-=1，不断重复
给你一个整数数组 arr 和两个整数 k 和 threshold . 请你返回长度为 k 且平均值大于等于 threshold 的子数组数目. LC1343 [x]
- 初始化滑窗 [0,k-2]（长度为k-1）计算和 c = sum(lis[0:k-1])
- 从左往右 i入，如果arr[i]+c>=k*threshold, 满足条件的子数组数目+1，将i-k+1对应的数退出滑窗 c-= arr[i-k+1]，不断重复
给你一个整数数组 nums 和一个整数 k . 请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：子数组的长度是 k，且子数组中的所有元素各不相同 . 返回满足题面要求的最大子数组和. 如果不存在子数组满足这些条件，返回 0 . 子数组是数组中一段连续非空的元素序列. LC2461
- 初始化滑窗[0,k-2]（长度为k-1），计算滑窗的和c，用哈希表记录滑窗元素出现的个数
- 从左到右入arr[i]，
交换定义为选中一个数组中的两个互不相同的位置并交换二者的值. 环形数组是一个数组，可以认为第一个元素和最后一个元素相邻 . 给你一个二进制环形数组 nums ，返回在任意位置将数组中的所有 1 聚集在一起需要的最少交换次数. LC2134
给你一个字符串 s ，请你返回满足以下条件且出现次数最大的任意子串的出现次数：子串中不同字母的数目必须小于等于 maxLetters . 子串的长度必须大于等于 minSize 且小于等于 maxSize . LC1297
给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引. 不考虑答案输出的顺序. （字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次. ）LC438
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列. 如果是，返回 true ；否则，返回 false . 换句话说，s1 的排列之一是 s2 的子串 . LC567
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧. 你只可以看到在滑动窗口内的 k 个数字. 滑动窗口每次只向右移动一位. 返回滑动窗口中的最大值 . LC239

不定长滑动窗口¶

不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，以及求子数组个数.

求最长¶

一般题目都有“至多”的要求.

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度. LC3
给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度. LC3090
给你一个二进制数组 nums ，你需要从中删掉一个元素. 请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度. 如果不存在这样的子数组，请返回 0 . LC1493
给你一个整数数组 nums 和一个整数 k . 一个元素 x 在数组中的频率指的是它在数组中的出现次数. 如果一个数组中所有元素的频率都小于等于 k ，那么我们称这个数组是好数组. 请你返回 nums 中最长好子数组的长度. 子数组指的是一个数组中一段连续非空的元素序列. LC2958
给你一个整数数组 nums 和一个整数 x . 每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值. 请注意，需要修改数组以供接下来的操作使用. 如果可以将 x 恰好减到 0 ，返回最小操作数；否则，返回 -1 . LC1658
给你一个下标从 0 开始的整数数组 nums 和一个整数 k . 如果子数组中所有元素都相等，则认为子数组是一个等值子数组 . 注意，空数组是等值子数组 . 从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度. 子数组是数组中一个连续且可能为空的元素序列. LC2831
给你一个整数数组 nums . 每一次操作中，你可以将 nums 中任意一个元素替换成任意整数. 如果 nums 满足以下条件，那么它是连续的：nums 中所有元素都是互不相同的. nums 中最大元素与最小元素的差等于nums.length - 1 . 比方说，nums = [4, 2, 5, 3] 是连续的，但是 nums = [1, 2, 3, 5, 6] 不是连续的 . 请你返回使 nums 连续的最少操作次数. LC2009

求最短¶

给定一个含有 n 个正整数的数组和一个正整数 target . 找出该数组中满足其总和大于等于 target 的长度最小的子数组 [nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r] ，并返回其长度. 如果不存在符合条件的子数组，返回 0 . LC209
给你一个二进制字符串 s 和一个正整数 k . 如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个美丽子字符串 . 令 len 等于最短美丽子字符串的长度. 返回长度等于 len 且字典序最小的美丽子字符串. 如果 s 中不含美丽子字符串，则返回一个空字符串. 对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序大于字符串 b . 例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c . LC2904
给你一个字符串 s 、一个字符串 t . 返回 s 中涵盖 t 所有字符的最小子串. 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" . LC76

求子数组个数¶

越长越合法

给你一个字符串 s ，它只包含三种字符 a, b 和 c . 请你返回 a，b 和 c 都至少出现过一次的子字符串数目. LC1358
给你一个整数数组 nums 和一个正整数 k . 请你统计有多少满足「 nums 中的最大元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目. 子数组是数组中的一个连续元素序列. LC2962
给你一个字符串 s 和一个整数 k，在 s 的所有子字符串中，请你统计并返回至少有一个字符至少出现 k 次的子字符串总数. 子字符串是字符串中的一个连续、非空的字符序列. LC3325

越短越合法

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目. LC713
给你一个二进制字符串 s 和一个整数 k. 如果一个二进制字符串满足以下任一条件，则认为该字符串满足 k 约束：字符串中 0 的数量最多为 k. 字符串中 1 的数量最多为 k. 返回一个整数，表示 s 的所有满足 k 约束的子字符串的数量. LC3258
一个数组的分数定义为数组之和乘以数组的长度. 比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 . 给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数严格小于 k 的非空整数子数组数目. 子数组是数组中的一个连续元素序列. LC2302

恰好型滑动窗口

例如，要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：

计算有多少个元素和 \(\geq\) k 的子数组.
计算有多少个元素和 \(>\) k，也就是 \(\geq\) k + 1 的子数组.

答案就是元素和 \(\geq\) k 的子数组个数，减去元素和 \(\geq\) k + 1 的子数组个数. 这里把 \(>\) 转换成 \(\geq\) ，从而可以把滑窗逻辑封装成一个函数 f，然后用 f(k) - f(k + 1) 计算，无需编写两份滑窗代码.

总结：“恰好” 可以拆分成两个 “至少”，也就是两个 “越长越合法” 的滑窗问题.

给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的非空子数组. 子数组是数组的一段连续部分. LC930
给你一个整数数组 nums 和一个整数 k. 如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是 “优美子数组”. 请返回这个数组中 “优美子数组” 的数目. LC1248
给定一个正整数数组 nums和一个整数 k，返回 nums 中 “好子数组” 的数目. 如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 “好子数组”. 例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3. 子数组是数组的连续部分. LC992