09 滑动窗口：找到字符串中所有字母异位词 438
2025-05-25 10:41:38 星期日目录
[*]1456.定长子串中元音的最大数目
[*]说一下我最开始的思路
[*]如何进一步优化呢
[*]让我们看一看灵神的做法
[*]438 找到字符串中所有字母异位词
[*]再试一下
[*]学习大神的思路和方法
[*]定长滑动窗口
[*]继续优化
[========]
1456.定长子串中元音的最大数目
说一下我最开始的思路
点击查看代码class Solution {
public:
int maxVowels(string s, int k) {
if (s.empty() || k == 0)
return 0;
unordered_set<char> st {'a', 'e', 'i', 'o', 'u'};
//定长滑动窗口
/*
时间复杂度：O(nk)
解释：外循环遍历n-k+1次,n是字符串长度
内循环遍历k次
如果k很大，那就是O(n^2)
Leecode会超时
空间复杂度：O(1)
*/
int left = 0, right = k;
int ans = INT_MIN;
int cnt = 0;
while (left < s.length() - k + 1) { //nk
for (int i = left; i < right; ++i) {
if (st.contains(s))
cnt++;
}
ans = max(ans, cnt);
cnt = 0;
++left, ++right;
}
return ans;
}
};如何进一步优化呢
我的想法是，内循环没有必要每次都检查已经重复的部分，因为定长滑动窗口滑动时只会去掉最左边的元素，加上最右边的元素，只要检查这两个就好了。
点击查看代码```C++class Solution {public: int maxVowels(string s, int k) { if (s.empty() || k == 0) return 0; unordered_set st {'a', 'e', 'i', 'o', 'u'}; //通过了，时间复杂度优化到O(n) //空间复杂度O(1) int left = 0, right = k; int ans = INT_MIN; int cnt = 0; for (int i = left; i < right; ++i) { if (st.contains(s)) cnt++; } ans = max(ans, cnt); while (left < s.length() - k + 1) { //滑动窗口向右滑动 if (st.contains(s)) { cnt++; } //去掉left的元素 if (st.contains(s)) { cnt--; } ans = max(ans, cnt); if (ans == k) break; ++left, ++right; } return ans; }};```妈呀，整整用了一个多小时，我真是笨死了。
让我们看一看灵神的做法
灵神的思路和我第二种是一样的，但是灵神的代码更加简洁优雅
点击查看代码class Solution {
public:
int maxVowels(string s, int k) {
int ans = 0, vowel = 0;
for (int i = 0; i < s.length(); i++) {
// 1. 进入窗口
if (s == 'a' || s == 'e' || s == 'i' || s == 'o' || s == 'u') {
vowel++;
}
if (i < k - 1) { // 窗口大小不足 k
continue;
}
// 2. 更新答案
ans = max(ans, vowel);
// 3. 离开窗口
char out = s;
if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
vowel--;
}
}
return ans;
}
};
作者：灵茶山艾府
链接：https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/solutions/2809359/tao-lu-jiao-ni-jie-jue-ding-chang-hua-ch-fzfo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。代码看完了，优雅，实在是太优雅了。
好了，这道题看完之后，我们可以来解决Leecode hot100上的异位词这道题了，这才是我们今天的目标（BOSS）
呜呜呜，一开始看这道题一个多小时愣是没写出来，怎么就难死我了呢？
[========]
438 找到字符串中所有字母异位词
再试一下
又是半个小时过去了。
额，我做不出来的原因是，如果这道题像刚才那样依然采用定长滑动窗口，那样每次我找到一个子串应该如何确定它就是它的异位词呢？
虽然说是可以排序，但是这样做的时间复杂度是\(O(n^{2}\log n)\)
不挣扎了，看人家是怎么做的吧。
学习大神的思路和方法
定长滑动窗口
点击查看代码class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
array<int, 26> cnt_p{}; // 统计 p 的每种字母的出现次数
array<int, 26> cnt_s{}; // 统计 s 的长为 p.length() 的子串 s' 的每种字母的出现次数
for (char c : p) {
cnt_p++;
}
for (int right = 0; right < s.length(); right++) {
cnt_s - 'a']++; // 右端点字母进入窗口
int left = right - p.length() + 1;
if (left < 0) { // 窗口长度不足 p.length()
continue;
}
if (cnt_s == cnt_p) { // s' 和 p 的每种字母的出现次数都相同
ans.push_back(left); // s' 左端点下标加入答案
}
cnt_s - 'a']--; // 左端点字母离开窗口
}
return ans;
}
};
作者：灵茶山艾府
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/2969498/liang-chong-fang-fa-ding-chang-hua-chuan-14pd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。确实是一样的套路。
有值得我借鉴和学习之处。
[*]array 和 vector 都重载了 == 运算符，可以比较整个数组是否相等；区别在于array是定长的，而vector可以动态向后扩展
分析上述解法的时间复杂度 和 空间复杂度
时间复杂度：\(O(|\sum|m+n)\)，\(|\sum|\)是字母表的长度26，m是滑动窗口滑动的次数，n是统计p的迭代次数
继续优化
点击查看代码class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
int cnt{}; // 统计 p 的每种字母的出现次数
for (char c : p) {
cnt++;
}
int left = 0;
for (int right = 0; right < s.size(); right++) {
int c = s - 'a';
cnt--; // 右端点字母进入窗口
while (cnt < 0) { // 字母 c 太多了
cnt - 'a']++; // 左端点字母离开窗口
left++;
}
if (right - left + 1 == p.length()) { // s' 和 p 的每种字母的出现次数都相同
ans.push_back(left); // s' 左端点下标加入答案
}
}
return ans;
}
};
作者：灵茶山艾府
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/2969498/liang-chong-fang-fa-ding-chang-hua-chuan-14pd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。不定长滑窗可以可以将时间复杂度优化至$O(m+n)，贴一下代码吧。
累死了，今天就到这里吧。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]