算法2：滑动窗口(下）

水果成篮

两元素排空操作
窗口中存在元素交错情况，以是出窗口肯定要出干净！！！

1. class Solution {
2. public:
3.     int totalFruit(vector<int>& fruits) {
4.         unordered_map<int, int> hash; // 统计水果情况
5.         int res = 0;
6.         for (int left = 0, right = 0; right < fruits.size(); right++) {
7.             hash[fruits[right]]++;  // 进窗口
8.             while (hash.size() > 2) // 判断
9.             {
10.                 // 出窗口
11.                 hash[fruits[left]]--;
12.                 if (hash[fruits[left]] == 0)
13.                     hash.erase(fruits[left]);
14.                 left++;
15.             }
16.             res = max(right - left + 1, res);
17.         }
18.         return res;
19.     }
20. };

复制代码

优化：

1. class Solution {
2. public:
3.     int totalFruit(vector<int>& fruits) {
4.         int hash[100001] = {0}; // 统计水果情况
5.         int res = 0;
6.         for (int left = 0, right = 0, kinds = 0; right < fruits.size();
7.              right++) {
8.             if (hash[fruits[right]] == 0)
9.                 kinds++;           // 维护水果种类
10.             hash[fruits[right]]++; // 进窗口
11.             while (kinds > 2)      // 判断
12.             {
13.                 // 出窗口
14.                 hash[fruits[left]]--;
15.                 if (hash[fruits[left]] == 0)
16.                     kinds--;
17.                 left++;
18.             }
19.             res = max(right - left + 1, res);
20.         }
21.         return res;
22.     }
23. };

复制代码

本领：数据有限的情况下，用数组比用容器快很多
找到字符串中所有字母异位词

1. class Solution {
2. public:
3.     vector<int> findAnagrams(string s, string p) {
4.         if (s.size() < p.size())
5.             return {};
7.         vector<int> res;
8.         long long sum = 0;
9.         for (auto e : p)
10.             sum += (e - '0') * (e - '0') * (e - '0');
12.         int left = 0, right = 0;
13.         long long target = 0;
14.         while (right < s.size()) {
15.             target += (s[right] - '0') * (s[right] - '0') * (s[right] - '0');
16.             while (target >= sum && left <= right) {
17.                 if (target == sum && right - left == p.size() - 1)
18.                     res.push_back(left);
19.                 target -= (s[left] - '0') * (s[left] - '0') * (s[left] - '0');
20.                 left++;
21.             }
22.             right++;
23.         }
24.         return res;
25.     }
26. };

复制代码

1. class Solution {
2. public:
3.     vector<int> findAnagrams(string s, string p) {
4.         if (s.size() < p.size())
5.             return {};
7.         int hash1[26] = {0};
8.         for (auto e : p)
9.             hash1[e - 'a']++;
11.         vector<int> res;
12.         int hash2[26] = {0};
13.         int m = p.size();
14.         for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
15.             char in = s[right];
16.             if (++hash2[in - 'a'] <= hash1[in - 'a']) // 进窗口及维护count
17.                 count++;
18.             if (right - left + 1 > m) // 判断
19.             {
20.                 char out = s[left++];
21.                 if (hash2[out - 'a']-- <= hash1[out - 'a'])
22.                     count--; // 出窗口及维护count
23.             }
24.             // 结果更新
25.             if (count == m)
26.                 res.push_back(left);
27.         }
29.         return res;
30.     }
31. };

复制代码

串联所有单词的子串*

1. class Solution {
2. public:
3.     vector<int> findSubstring(string s, vector<string>& words) {
4.         int slen = s.size(), plen = words.size(), _size = words[0].size();
5.         plen *= _size;
6.         if (plen == 0 || slen < plen)
7.             return {};
9.         // 滑动窗口+哈希表
10.         vector<int> res;
11.         unordered_map<string, int> aCount;
12.         for (auto& e : words)
13.             aCount[e]++;
15.         unordered_map<string, int> bCount;
16.         int n = words[0].size();
17.         while (n--) /// 执行n次滑动窗口
18.         {
20.             for (int left = n, right = n, count = 0; right + _size <= s.size();
21.                  right += words[0].size()) {
22.                 string in = s.substr(right, words[0].size());
23.                 bCount[in]++;
24.                 // if(aCount[in] && bCount[in] <= aCount[in])   count++;
25.                 if (aCount.count(in) && bCount[in] <= aCount[in])
26.                     count++;
28.                 // 这里窗口的长度是right + len -left,
29.                 // 也就是说窗口的长度已经大于words的总体长度
30.                 if (right - left == words[0].size() * words.size()) {
31.                     string out = s.substr(left, words[0].size());
33.                     // 这里用[]会影响速度，用哈希的计数函数快一些
34.                     // count函数的返回值是0或1
35.                     // ，类似于bool值，表示其是否存在，而[]返回的是次数，就涉及到了查找，故花费时间较长
36.                     if (aCount.count(out) && bCount[out] <= aCount[out])
37.                         count--;
38.                     // if(aCount[out] && bCount[out] <= aCount[out]) count--;
40.                     bCount[out]--;
41.                     left += words[0].size();
42.                 }
44.                 if (count == words.size())
45.                     res.push_back(left);
46.             }
47.             bCount.clear();
48.         }
49.         return res;
50.     }
51. };
53. ```cpp
54. class Solution {
55. public:
56.     vector<int> findSubstring(string s, vector<string>& words) {
57.         vector<int> result;
58.         if (s.empty() || words.empty())
59.             return result;
61.         int word_length = words[0].length();
62.         int num_words = words.size();
63.         int total_length = word_length * num_words;
65.         unordered_map<string, int> word_count;
66.         for (const string& word : words) {
67.             word_count[word]++;
68.         }
70.         for (int i = 0; i < word_length; ++i) {
71.             int left = i, right = i;
72.             unordered_map<string, int> window_count;
74.             while (right + word_length <= s.length()) {
75.                 string word = s.substr(right, word_length);
76.                 right += word_length;
78.                 if (word_count.find(word) != word_count.end()) {
79.                     window_count[word]++;
81.                     while (window_count[word] > word_count[word]) {
82.                         string left_word = s.substr(left, word_length);
83.                         window_count[left_word]--;
84.                         left += word_length;
85.                     }
87.                     if (right - left == total_length) {
88.                         result.push_back(left);
89.                     }
90.                 } else {
91.                     window_count.clear();
92.                     left = right;
93.                 }
94.             }
95.         }
96.         return result;
97.     }
98. };

复制代码

两段代码都是：哈希+滑动窗口，时间空间复杂度也一样，但是测试时间却减少了许多，可以对比一下第二段代码优于第一段代码的点在哪里？
最小覆盖子串*

1. class Solution {
2. public:
3.     string minWindow(string s, string t) {
4.         string res;
5.         int hash[128] = {0};
6.         int tt = 0; // 字符种类
7.         for (char& e : t)
8.             if (0 == hash[e]++)
9.                 tt++;
11.         int hash1[128] = {0};
12.         int begin = -1, m = INT_MAX;
13.         for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
14.             // 进窗口
15.             char in = s[right];
16.             if (++hash1[in] == hash[in])
17.                 count++;
18.             //  检查
19.             while (count == tt) {
20.                 //  更新
21.                 if (right - left + 1 < m) {
22.                     begin = left;
23.                     m = right - left + 1;
24.                 }
25.                 //  出窗口
26.                 char out = s[left++];
27.                 if (hash1[out]-- == hash[out])
28.                     count--;
29.             }
30.         }
31.         if (begin != -1)
32.             res = s.substr(begin, m);
33.         return res;
34.     }
35. };
36. //  "ADOBEC"

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。