滑动窗口与双指针

一.定长滑动窗口

大致套路：


示例 1，s=abciiidef, 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 的元素离开窗口，更新相关统计量

模板题：

定长字串中元音的最大数目

给你字符串 s 和整数 k 
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans = vowel = 0
        for i, c in enumerate(s):
            if c in "aeiou":
                vowel += 1
            if i < k - 1:
                continue
            ans = max(ans, vowel)
            if s[i - k + 1] in "aeiou":
                vowel -= 1
        return ans

https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/

类别：

  1. 维护定长滑动窗口和
    1343. 大小为 K 且平均值大于等于阈值的子数组数目1317
    2090. 半径为 k 的子数组平均值 1358
    2379. 得到 K 个黑块的最少涂色次数 1360

  2. 维护定长滑动窗口 + 字典计数
    2841. 几乎唯一子数组的最大和 1546
    2461. 长度为 K 子数组中的最大和 1553

  3. 思维上的考察
    1423. 可获得的最大点数 1574
    1052. 爱生气的书店老板