📍前言
本篇将学习前缀和OJ题定长子串中元音的最大数目相关知识。
🕺作者： 迷茫的启明星
学习路线
C语言从0到1
C++初阶
数据结构从0到1
😘欢迎关注：👍点赞🙌收藏✍️留言
🏇码字不易，你的👍点赞🙌收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！
持续更新中~
【前缀和】1456. 定长子串中元音的最大数目
问题描述
给定一个字符串 s 和一个整数 k，要求找到 s 中包含最多元音的字符子串，并返回其长度。其中，元音字母包括 a, e, i, o, 和 u。
暴力解法
一种直观的解法是遍历所有可能的子字符串，并统计其中元音字母的数量。这种方法的时间复杂度为 O(n^2)，其中 n 为字符串 s 的长度。当字符串长度较大时，这种解法会超时。
class Solution { public: bool check(char x) { string es="aeiou"; for(int i=0;i<es.size();++i) { if(es[i]==x)return true; } return false; } int maxVowels(string s, int k) { int flag=0; int maxn=0; for(int i=0;i<s.size()-k+1;i++) { for(int j=i;j<i+k;++j) { if(check(s[j]))flag++; } maxn=max(flag,maxn); flag=0; } return maxn; } };
滑动窗口算法
为了降低时间复杂度，我们可以采用滑动窗口算法。滑动窗口算法通过维护一个固定大小的窗口，在字符串上滑动，从而避免了对每个子字符串的重复计算。
窗口滑动
首先，我们需要初始化一个窗口大小为 k 的滑动窗口。然后，从左到右滑动窗口，并统计窗口内元音字母的数量。在滑动过程中，我们需要更新窗口内元音字母的数量，并在找到最大元音数量时更新结果。
class Solution { public: bool check(char x) { string es="aeiou"; for(int i=0;i<es.size();++i) { if(es[i]==x)return true; } return false; } int maxVowels(string s, int k) { int nums[s.size()]; nums[0] = check(s[0]) ? 1 : 0; int maxn = nums[k - 1]; for(int j = k; j < s.size(); ++j) { maxn = max(maxn, nums[j] - nums[j - k]); } return maxn; } };
优化
在这个解法中，我们仍然需要遍历整个字符串。为了进一步提高效率，我们可以在初始化滑动窗口时，直接计算前 k 个字符的元音数量，从而避免在滑动过程中重复计算。
class Solution { public: bool check(char x) { string es="aeiou"; for(int i=0;i<es.size();++i) { if(es[i]==x)return true; } return false; } int maxVowels(string s, int k) { int nums[s.size()]; nums[0] = check(s[0]) ? 1 : 0; for(int i = 1; i < s.size(); ++i) { nums[i] = nums[i - 1] + (check(s[i]) ? 1 : 0); } int maxn = nums[k - 1]; for(int j = k; j < s.size(); ++j) { maxn = max(maxn, nums[j] - nums[j - k]); } return maxn; } };
官方题解：
解题思路：
我们可以使用滑动窗口的方法来解决这个问题。首先，定义一个isVowel函数用于判断字符是否为元音。然后，初始化两个指针left和right，分别表示窗口的左右边界。初始时，left指针指向字符串s的第一个字符，right指针指向left指针的下一个字符。
1.初始化一个变量vowel_count用于记录当前窗口内的元音字符个数。
2.在每次循环中，先更新vowel_count，然后将当前vowel_count与ans进行比较，取最大值。
3.如果right指针没有越界，则将right指针向右移动一个位置，同时更新窗口内的元音字符个数。
4.如果right指针已经越界，则将left指针向右移动一个位置，同时更新窗口内的元音字符个数。
5.重复步骤2-4，直到right指针到达字符串s的末尾。
代码实现：
class Solution { public: bool isVowel(char ch) { return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'; } int maxVowels(string s, int k) { int n = s.size(); int vowel_count = 0; int left = 0, right = 0; int ans = 0; while (right < n) { vowel_count += isVowel(s[right]); ++right; if (right - left == k) { ans = max(ans, vowel_count); vowel_count -= isVowel(s[left]); ++left; } } return ans; } };
总结：
这个官方题解采用了滑动窗口的方法来解决问题。通过维护一个固定大小的窗口，我们可以在O(n)的时间复杂度内找到最长连续元音字符的子串。在实际编程中，可以根据具体需求对这个解法进行优化，例如在字符串中只包含元音字符的情况下，可以进一步优化时间复杂度。
