09 滑动窗口：找到字符串中所有字母异位词 438

2025-05-25 10:41:38 星期日

目录

• 1456.定长子串中元音的最大数目
  
  
  
  • 说一下我最开始的思路
    
  
  
• 如何进一步优化呢
  
• 让我们看一看灵神的做法
  
• 438 找到字符串中所有字母异位词
  
  
  
  • 再试一下
    
  • 学习大神的思路和方法
    
    
    
    • 定长滑动窗口
      
    • 继续优化
      
    
    
  
  

[========]
1456.定长子串中元音的最大数目

说一下我最开始的思路

点击查看代码

1. class Solution {
2. public:
3.     int maxVowels(string s, int k) {
4.         if (s.empty() || k == 0)
5.             return 0;
6.         unordered_set<char> st {'a', 'e', 'i', 'o', 'u'};
7.         //定长滑动窗口
8.         /*
9.             时间复杂度：O(nk)
10.             解释：外循环遍历n-k+1次,n是字符串长度
11.                   内循环遍历k次
12.             如果k很大，那就是O(n^2)
13.             Leecode会超时
14.             空间复杂度：O(1)
15.         */
16.         int left = 0, right = k;
17.         int ans = INT_MIN;
18.         int cnt = 0;
19.         while (left < s.length() - k + 1) { //nk
20.             for (int i = left; i < right; ++i) {
21.                 if (st.contains(s[i]))
22.                     cnt++;
23.             }
24.             ans = max(ans, cnt);
25.             cnt = 0;
26.             ++left, ++right;
27.         }
28.         return ans;
29.     }
30. };

复制代码

如何进一步优化呢

我的想法是，内循环没有必要每次都检查已经重复的部分，因为定长滑动窗口滑动时只会去掉最左边的元素，加上最右边的元素，只要检查这两个就好了。
点击查看代码```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[right])) {                cnt++;            }            //去掉left的元素            if (st.contains(s[left])) {                cnt--;            }            ans = max(ans, cnt);            if (ans == k)                break;            ++left, ++right;            }        return ans;    }};```妈呀，整整用了一个多小时，我真是笨死了。
让我们看一看灵神的做法

灵神的思路和我第二种是一样的，但是灵神的代码更加简洁优雅
点击查看代码

1. class Solution {
2. public:
3.     int maxVowels(string s, int k) {
4.         int ans = 0, vowel = 0;
5.         for (int i = 0; i < s.length(); i++) {
6.             // 1. 进入窗口
7.             if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
8.                 vowel++;
9.             }
10.             if (i < k - 1) { // 窗口大小不足 k
11.                 continue;
12.             }
13.             // 2. 更新答案
14.             ans = max(ans, vowel);
15.             // 3. 离开窗口
16.             char out = s[i - k + 1];
17.             if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
18.                 vowel--;
19.             }
20.         }
21.         return ans;
22.     }
23. };
25. 作者：灵茶山艾府
26. 链接：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/
27. 来源：力扣（LeetCode）
28. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制代码

代码看完了，优雅，实在是太优雅了。
好了，这道题看完之后，我们可以来解决Leecode hot100上的异位词这道题了，这才是我们今天的目标（BOSS）
呜呜呜，一开始看这道题一个多小时愣是没写出来，怎么就难死我了呢？
[========]
438 找到字符串中所有字母异位词

再试一下

又是半个小时过去了。
额，我做不出来的原因是，如果这道题像刚才那样依然采用定长滑动窗口，那样每次我找到一个子串应该如何确定它就是它的异位词呢？
虽然说是可以排序，但是这样做的时间复杂度是\(O(n^{2}\log n)\)
不挣扎了，看人家是怎么做的吧。
学习大神的思路和方法

定长滑动窗口

点击查看代码

1. class Solution {
2. public:
3.     vector<int> findAnagrams(string s, string p) {
4.         vector<int> ans;
5.         array<int, 26> cnt_p{}; // 统计 p 的每种字母的出现次数
6.         array<int, 26> cnt_s{}; // 统计 s 的长为 p.length() 的子串 s' 的每种字母的出现次数
7.         for (char c : p) {
8.             cnt_p[c - 'a']++;
9.         }
10.         for (int right = 0; right < s.length(); right++) {
11.             cnt_s[s[right] - 'a']++; // 右端点字母进入窗口
12.             int left = right - p.length() + 1;
13.             if (left < 0) { // 窗口长度不足 p.length()
14.                 continue;
15.             }
16.             if (cnt_s == cnt_p) { // s' 和 p 的每种字母的出现次数都相同
17.                 ans.push_back(left); // s' 左端点下标加入答案
18.             }
19.             cnt_s[s[left] - 'a']--; // 左端点字母离开窗口
20.         }
21.         return ans;
22.     }
23. };
25. 作者：灵茶山艾府
26. 链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/2969498/liang-chong-fang-fa-ding-chang-hua-chuan-14pd/
27. 来源：力扣（LeetCode）
28. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制代码

确实是一样的套路。
有值得我借鉴和学习之处。

• array 和 vector 都重载了 == 运算符，可以比较整个数组是否相等；区别在于array是定长的，而vector可以动态向后扩展
  

分析上述解法的时间复杂度 和 空间复杂度
时间复杂度：\(O(|\sum|m+n)\)，\(|\sum|\)是字母表的长度26，m是滑动窗口滑动的次数，n是统计p的迭代次数
继续优化

点击查看代码

1. class Solution {
2. public:
3.     vector<int> findAnagrams(string s, string p) {
4.         vector<int> ans;
5.         int cnt[26]{}; // 统计 p 的每种字母的出现次数
6.         for (char c : p) {
7.             cnt[c - 'a']++;
8.         }
9.         int left = 0;
10.         for (int right = 0; right < s.size(); right++) {
11.             int c = s[right] - 'a';
12.             cnt[c]--; // 右端点字母进入窗口
13.             while (cnt[c] < 0) { // 字母 c 太多了
14.                 cnt[s[left] - 'a']++; // 左端点字母离开窗口
15.                 left++;
16.             }
17.             if (right - left + 1 == p.length()) { // s' 和 p 的每种字母的出现次数都相同
18.                 ans.push_back(left); // s' 左端点下标加入答案
19.             }
20.         }
21.         return ans;
22.     }
23. };
25. 作者：灵茶山艾府
26. 链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/2969498/liang-chong-fang-fa-ding-chang-hua-chuan-14pd/
27. 来源：力扣（LeetCode）
28. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制代码

不定长滑窗可以可以将时间复杂度优化至$O(m+n)，贴一下代码吧。
累死了，今天就到这里吧。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！