兩元素排空操作
窗口中存在元素交錯情況，所以出窗口一定要出干凈！！！

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int, int> hash; // 統計水果情況int res = 0;for (int left = 0, right = 0; right < fruits.size(); right++) {hash[fruits[right]]++;  // 進窗口while (hash.size() > 2) // 判斷{// 出窗口hash[fruits[left]]--;if (hash[fruits[left]] == 0)hash.erase(fruits[left]);left++;}res = max(right - left + 1, res);}return res;}
};

優化：

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001] = {0}; // 統計水果情況int res = 0;for (int left = 0, right = 0, kinds = 0; right < fruits.size();right++) {if (hash[fruits[right]] == 0)kinds++;           // 維護水果種類hash[fruits[right]]++; // 進窗口while (kinds > 2)      // 判斷{// 出窗口hash[fruits[left]]--;if (hash[fruits[left]] == 0)kinds--;left++;}res = max(right - left + 1, res);}return res;}
};

技巧：數據有限的情況下，用數組比用容器快很多

class Solution {
public:vector<int> findAnagrams(string s, string p) {if (s.size() < p.size())return {};vector<int> res;long long sum = 0;for (auto e : p)sum += (e - '0') * (e - '0') * (e - '0');int left = 0, right = 0;long long target = 0;while (right < s.size()) {target += (s[right] - '0') * (s[right] - '0') * (s[right] - '0');while (target >= sum && left <= right) {if (target == sum && right - left == p.size() - 1)res.push_back(left);target -= (s[left] - '0') * (s[left] - '0') * (s[left] - '0');left++;}right++;}return res;}
};

class Solution {
public:vector<int> findAnagrams(string s, string p) {if (s.size() < p.size())return {};int hash1[26] = {0};for (auto e : p)hash1[e - 'a']++;vector<int> res;int hash2[26] = {0};int m = p.size();for (int left = 0, right = 0, count = 0; right < s.size(); right++) {char in = s[right];if (++hash2[in - 'a'] <= hash1[in - 'a']) // 進窗口及維護countcount++;if (right - left + 1 > m) // 判斷{char out = s[left++];if (hash2[out - 'a']-- <= hash1[out - 'a'])count--; // 出窗口及維護count}// 結果更新if (count == m)res.push_back(left);}return res;}
};

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {int slen = s.size(), plen = words.size(), _size = words[0].size();plen *= _size;if (plen == 0 || slen < plen)return {};// 滑動窗口+哈希表vector<int> res;unordered_map<string, int> aCount;for (auto& e : words)aCount[e]++;unordered_map<string, int> bCount;int n = words[0].size();while (n--) /// 執行n次滑動窗口{for (int left = n, right = n, count = 0; right + _size <= s.size();right += words[0].size()) {string in = s.substr(right, words[0].size());bCount[in]++;// if(aCount[in] && bCount[in] <= aCount[in])   count++;if (aCount.count(in) && bCount[in] <= aCount[in])count++;// 這里窗口的長度是right + len -left,// 也就是說窗口的長度已經大于words的總體長度if (right - left == words[0].size() * words.size()) {string out = s.substr(left, words[0].size());// 這里用[]會影響速度，用哈希的計數函數快一些// count函數的返回值是0或1// ，類似于bool值，表示其是否存在，而[]返回的是次數，就涉及到了查找，故花費時間較長if (aCount.count(out) && bCount[out] <= aCount[out])count--;// if(aCount[out] && bCount[out] <= aCount[out]) count--;bCount[out]--;left += words[0].size();}if (count == words.size())res.push_back(left);}bCount.clear();}return res;}
};```cpp
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> result;if (s.empty() || words.empty())return result;int word_length = words[0].length();int num_words = words.size();int total_length = word_length * num_words;unordered_map<string, int> word_count;for (const string& word : words) {word_count[word]++;}for (int i = 0; i < word_length; ++i) {int left = i, right = i;unordered_map<string, int> window_count;while (right + word_length <= s.length()) {string word = s.substr(right, word_length);right += word_length;if (word_count.find(word) != word_count.end()) {window_count[word]++;while (window_count[word] > word_count[word]) {string left_word = s.substr(left, word_length);window_count[left_word]--;left += word_length;}if (right - left == total_length) {result.push_back(left);}} else {window_count.clear();left = right;}}}return result;}
};

兩段代碼都是：哈希+滑動窗口，時間空間復雜度也一樣，但是測試時間卻減少了許多，可以對比一下第二段代碼優于第一段代碼的點在哪里？

class Solution {
public:string minWindow(string s, string t) {string res;int hash[128] = {0};int tt = 0; // 字符種類for (char& e : t)if (0 == hash[e]++)tt++;int hash1[128] = {0};int begin = -1, m = INT_MAX;for (int left = 0, right = 0, count = 0; right < s.size(); right++) {// 進窗口char in = s[right];if (++hash1[in] == hash[in])count++;//  檢查while (count == tt) {//  更新if (right - left + 1 < m) {begin = left;m = right - left + 1;}//  出窗口char out = s[left++];if (hash1[out]-- == hash[out])count--;}}if (begin != -1)res = s.substr(begin, m);return res;}
};
//  "ADOBEC"