本文以“长度为 k 的子字符串中最多能包含多少个元音字母”为例，系统讲解定长滑动窗口的核心思想、代码模板、正确性分析以及常见错误。

---

一、问题描述

给定一个字符串 s 和一个整数 k，返回字符串 s 中所有长度为 k 的子字符串里，能够包含的最大元音字母数量。

英文中的元音字母为：

a、e、i、o、u

示例 1

输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 中包含 3 个元音字母。

示例 2

输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3

输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。

示例 4

输入：s = "rhythms", k = 4
输出：0
解释：字符串中不存在元音字母。

---

二、问题的关键特征

这道题有三个非常明显的特征：

1. 需要处理字符串中的连续子串；
2. 每个子串的长度固定为 k；
3. 需要统计每个子串中的元音字母数量，并求最大值。

其中，“连续区间”和“固定长度”是使用定长滑动窗口的重要信号。

---

三、暴力枚举思路

最直接的做法是枚举每一个长度为 k 的子字符串，然后统计其中元音字母的数量。

字符串长度为 n 时，一共有：

n - k + 1

个长度为 k 的子字符串。

对于每一个子字符串，都需要遍历 k 个字符进行统计，因此时间复杂度为：

O((n - k + 1) × k)

通常写作：

O(nk)

暴力代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set("aeiou")
        answer = 0

        for left in range(len(s) - k + 1):
            count = 0

            for index in range(left, left + k):
                if s[index] in vowels:
                    count += 1

            answer = max(answer, count)

        return answer

这段代码逻辑没有问题，但存在大量重复计算。

例如，窗口从：

s[0:k]

移动到：

s[1:k+1]

时，两个窗口中有 k - 1 个字符是相同的。

暴力算法却重新统计了整个窗口，没有复用上一个窗口的结果。

---

四、滑动窗口的核心思想

假设当前窗口为：

s[left:right+1]

并且窗口长度固定为 k。

当窗口向右移动一格时：

• 原窗口最左侧字符离开；
• 新窗口最右侧字符进入；
• 中间的 k - 1 个字符保持不变。

因此，新窗口中的元音数量可以由旧窗口快速计算得到：

新窗口元音数
=
旧窗口元音数
- 离开窗口的字符是否为元音
+ 进入窗口的字符是否为元音

用公式表示：

windowCount'
=
windowCount
- isVowel(s[right - k])
+ isVowel(s[right])

每次移动只需要进行一次删除和一次添加，不需要重新遍历整个窗口。

这正是滑动窗口能够将时间复杂度从 O(nk) 优化到 O(n) 的原因。

---

五、定长滑动窗口的执行过程

定长滑动窗口通常分为两个阶段。

1. 初始化第一个窗口

先统计字符串前 k 个字符中的元音数量：

window_count = 0

for index in range(k):
    if s[index] in vowels:
        window_count += 1

此时窗口覆盖：

s[0:k]

2. 向右移动窗口

从下标 k 开始，依次让新的字符进入窗口。

假设当前进入窗口的字符下标为 right，那么离开窗口的字符下标为：

right - k

更新过程为：

if s[right] in vowels:
    window_count += 1

if s[right - k] in vowels:
    window_count -= 1

每次更新后，用当前窗口的统计结果更新最大值。

---

六、完整代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set("aeiou")

        # 统计第一个长度为 k 的窗口
        window_count = sum(char in vowels for char in s[:k])
        answer = window_count

        # 从第二个窗口开始向右滑动
        for right in range(k, len(s)):
            # 新字符进入窗口
            if s[right] in vowels:
                window_count += 1

            # 最左侧字符离开窗口
            if s[right - k] in vowels:
                window_count -= 1

            answer = max(answer, window_count)

            # 长度为 k 的窗口最多只能包含 k 个元音
            if answer == k:
                return k

        return answer

---

七、代码逐行解析

1. 建立元音集合

vowels = set("aeiou")

使用集合可以快速判断一个字符是否为元音：

char in vowels

由于集合中只有五个字符，这里的判断可以视为常数时间操作。

---

2. 初始化第一个窗口

window_count = sum(char in vowels for char in s[:k])

在 Python 中，布尔值可以参与整数运算：

True  == 1
False == 0

因此：

sum(char in vowels for char in s[:k])

等价于统计前 k 个字符中有多少个字符属于元音集合。

例如：

s[:3] = "abc"

判断结果为：

a in vowels -> True
b in vowels -> False
c in vowels -> False

求和结果为：

1 + 0 + 0 = 1

---

3. 枚举进入窗口的新字符

for right in range(k, len(s)):

第一个窗口已经处理了下标：

0 到 k - 1

因此，第二个窗口中新进入的字符下标从 k 开始。

---

4. 加入右侧字符

if s[right] in vowels:
    window_count += 1

如果新进入窗口的字符是元音，当前窗口元音数量加一。

---

5. 移除左侧字符

if s[right - k] in vowels:
    window_count -= 1

当下标为 right 的字符进入窗口时，下标为 right - k 的字符离开窗口。

例如，k = 3，当 right = 3 时：

原窗口下标：[0, 1, 2]
新窗口下标：[1, 2, 3]

进入窗口的是：

s[3]

离开窗口的是：

s[3 - 3] = s[0]

---

6. 更新答案

answer = max(answer, window_count)

answer 保存目前为止所有长度为 k 的窗口中的最大元音数量。

---

7. 提前结束

if answer == k:
    return k

长度为 k 的窗口最多只能包含 k 个元音。

一旦某个窗口已经包含 k 个元音，就已经取得理论最大值，后续不可能出现更优答案，因此可以直接返回。

这一步不是必须的，但可以减少不必要的遍历。

---

八、示例推演

以：

s = "abciiidef"
k = 3

为例。

初始化第一个窗口

窗口："abc"
元音数量：1

此时：

window_count = 1
answer = 1

窗口滑动过程

窗口	离开的字符	进入的字符	当前元音数	最大元音数
abc	-	-	1	1
bci	a	i	1	1
cii	b	i	2	2
iii	c	i	3	3

当窗口移动到 "iii" 时，元音数量达到 k = 3，已经取得最大可能值，可以立即返回 3。

---

九、正确性分析

要证明算法正确，需要说明 window_count 在每次循环后始终等于当前窗口中的元音数量。

初始化阶段

算法首先统计 s[0:k] 中的所有元音，因此初始化后的 window_count 正确表示第一个窗口中的元音数量。

窗口移动阶段

当窗口向右移动一格时：

• s[right] 进入窗口；
• s[right - k] 离开窗口；
• 其余字符仍然保留在窗口中。

算法对进入窗口的元音执行加一，对离开窗口的元音执行减一，因此更新后的 window_count 正好等于新窗口中的元音数量。

算法遍历了所有长度为 k 的子字符串，并使用 answer 保存其中最大的元音数量，因此最终返回值就是题目要求的答案。

---

十、复杂度分析

设字符串长度为 n。

时间复杂度

初始化第一个窗口需要遍历 k 个字符，随后窗口移动 n - k 次，每次只进行常数次操作。

因此总时间复杂度为：

O(k) + O(n - k) = O(n)

空间复杂度

元音集合的大小固定为 5，不随输入规模变化，因此额外空间复杂度为：

O(1)

---

十一、定长滑动窗口通用模板

这道题可以抽象为一个非常通用的定长滑动窗口模板。

def fixed_window(nums, k):
    # 1. 初始化第一个窗口
    window_state = initialize(nums[:k])
    answer = window_state

    # 2. 从第二个窗口开始滑动
    for right in range(k, len(nums)):
        # 新元素进入窗口
        window_state = add(window_state, nums[right])

        # 旧元素离开窗口
        window_state = remove(window_state, nums[right - k])

        # 更新答案
        answer = update_answer(answer, window_state)

    return answer

对于求窗口元素和的问题，可以进一步写成：

def max_window_sum(nums, k):
    window_sum = sum(nums[:k])
    answer = window_sum

    for right in range(k, len(nums)):
        window_sum += nums[right]
        window_sum -= nums[right - k]
        answer = max(answer, window_sum)

    return answer

这道元音题与窗口最大和的本质完全相同，只是将“元素值”替换成了“字符是否为元音”。

可以定义：

value(char) =
    1，char 是元音
    0，char 不是元音

于是题目就转化成了：

求长度为 k 的连续区间中，元素和的最大值。

---

十二、为什么离开窗口的下标是 right - k

这是定长滑动窗口中最容易写错的地方。

当 right 表示新进入窗口的元素下标时，当前窗口应该覆盖：

[right - k + 1, right]

窗口长度为：

right - (right - k + 1) + 1 = k

在新字符进入之前，旧窗口覆盖：

[right - k, right - 1]

因此，需要移除的元素正是：

nums[right - k]

记忆方式：

进入下标：right
离开下标：right - k

---

十三、常见错误

错误 1：先加入新字符，却没有移除旧字符

for right in range(k, len(s)):
    if s[right] in vowels:
        window_count += 1

这样窗口会不断变大，不再是长度固定为 k 的窗口。

正确做法是每加入一个字符，就移除一个字符。

---

错误 2：离开窗口的下标写成 right - k + 1

错误写法：

s[right - k + 1]

right - k + 1 是新窗口左端点，而不是刚刚离开窗口的字符。

正确下标应为：

s[right - k]

---

错误 3：忘记统计第一个窗口

如果直接从 right = k 开始移动，却没有提前统计 s[:k]，那么第一个窗口会被遗漏。

标准写法应先完成：

window_count = ...
answer = window_count

然后再开始滑动。

---

错误 4：每次仍然重新统计整个窗口

for right in range(k - 1, len(s)):
    count = sum(char in vowels for char in s[right - k + 1:right + 1])

虽然代码中出现了“窗口”，但每次仍然遍历了 k 个字符，时间复杂度依旧是 O(nk)，并没有真正利用滑动窗口的增量更新思想。

滑动窗口优化的关键不是使用两个下标，而是：

复用旧窗口的计算结果，只处理进入和离开的元素。

---

十四、另一种更简洁的 Python 写法

由于 Python 中布尔值可以作为整数使用，窗口更新可以写得更加紧凑：

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set("aeiou")

        window_count = sum(char in vowels for char in s[:k])
        answer = window_count

        for right in range(k, len(s)):
            window_count += s[right] in vowels
            window_count -= s[right - k] in vowels
            answer = max(answer, window_count)

        return answer

这一写法与前面的实现完全等价。

不过在团队开发或面向初学者的代码中，使用显式的 if 判断通常具有更好的可读性。

---

十五、Java 实现

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> vowels = new HashSet<>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');

        int windowCount = 0;

        // 初始化第一个窗口
        for (int i = 0; i < k; i++) {
            if (vowels.contains(s.charAt(i))) {
                windowCount++;
            }
        }

        int answer = windowCount;

        // 向右滑动窗口
        for (int right = k; right < s.length(); right++) {
            if (vowels.contains(s.charAt(right))) {
                windowCount++;
            }

            if (vowels.contains(s.charAt(right - k))) {
                windowCount--;
            }

            answer = Math.max(answer, windowCount);

            if (answer == k) {
                return k;
            }
        }

        return answer;
    }
}

由于元音字符只有五个，也可以编写一个判断函数，避免创建集合：

private boolean isVowel(char c) {
    return c == 'a'
        || c == 'e'
        || c == 'i'
        || c == 'o'
        || c == 'u';
}

完整写法如下：

class Solution {
    public int maxVowels(String s, int k) {
        int windowCount = 0;

        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) {
                windowCount++;
            }
        }

        int answer = windowCount;

        for (int right = k; right < s.length(); right++) {
            if (isVowel(s.charAt(right))) {
                windowCount++;
            }

            if (isVowel(s.charAt(right - k))) {
                windowCount--;
            }

            answer = Math.max(answer, windowCount);

            if (answer == k) {
                return k;
            }
        }

        return answer;
    }

    private boolean isVowel(char c) {
        return c == 'a'
            || c == 'e'
            || c == 'i'
            || c == 'o'
            || c == 'u';
    }
}

---

十六、定长滑动窗口与不定长滑动窗口的区别

滑动窗口通常分为两类。

定长滑动窗口

窗口长度始终为固定值 k。

典型问题包括：

• 长度为 k 的子数组最大和；
• 长度为 k 的子串中最多的元音数量；
• 长度为 k 的子数组平均值；
• 长度为 k 的子数组中不同元素的最大数量。

定长窗口的特点是：

每进入一个元素，就必须移除一个元素。

---

不定长滑动窗口

窗口长度会根据条件动态扩大或缩小。

典型问题包括：

• 无重复字符的最长子串；
• 和大于等于目标值的最短子数组；
• 至多包含 k 种字符的最长子串；
• 最小覆盖子串。

不定长窗口通常采用以下结构：

left = 0

for right in range(len(nums)):
    # 将 nums[right] 加入窗口

    while window_not_valid:
        # 移除 nums[left]
        left += 1

    # 更新答案

两者最本质的区别是：

• 定长窗口通过下标关系保证窗口长度为 k；
• 不定长窗口通过条件判断决定何时移动左边界。

---

十七、如何识别定长滑动窗口题目

当题目中出现以下关键词时，可以优先考虑定长滑动窗口：

连续子数组
连续子字符串
长度恰好为 k
每连续 k 个元素
大小为 k 的区间
固定天数
固定时间段

进一步判断状态是否能够增量维护：

新窗口状态
=
旧窗口状态
- 离开元素的贡献
+ 进入元素的贡献

只要这个关系成立，通常就可以使用定长滑动窗口。

---

十八、可扩展问题

掌握本题后，可以进一步思考以下变化。

1. 长度为 k 的子串中辅音字母的最大数量

只需要将字符贡献改为：

char not in vowels

---

2. 长度为 k 的子串中不同字符的最大数量

需要使用哈希表维护窗口内每个字符的出现次数。

核心更新过程仍然是：

新字符进入
旧字符离开
更新窗口状态

---

3. 长度为 k 的子数组最大平均值

只需要维护窗口元素和：

最大平均值 = 最大窗口和 / k

---

4. 判断是否存在包含 k 个元音的长度为 k 的子串

一旦：

window_count == k

就可以返回 True。

---

十九、总结

定长滑动窗口的核心并不复杂，可以概括为四步：

1. 统计第一个窗口；
2. 新元素进入窗口；
3. 旧元素离开窗口；
4. 更新最终答案。

对于本题，窗口中维护的状态是“元音字母数量”。

状态转移关系为：

当前窗口元音数
=
上一个窗口元音数
+ 新进入字符的贡献
- 离开字符的贡献

最终实现将暴力算法的时间复杂度：

O(nk)

优化为：

O(n)

在面对“连续区间 + 固定长度”的问题时，应首先思考：

相邻两个窗口之间有哪些内容没有变化？能否只更新进入和离开的元素？

一旦能够复用前一个窗口的计算结果，滑动窗口往往就是最自然、最高效的解决方案。