目錄
小結以及代碼框架
76. 最小覆蓋子串
滑動窗口
代碼以及注釋
567. 字符串的排列
滑動窗口
438. 找到字符串中所有字母異位詞
3. 無重復字符的最長子串
化簡框架
reference

小結以及代碼框架

滑動窗口技巧屬于雙指針技巧。
該算法的思路為維護一個窗口，不斷滑動，然后更新答案。
大致框架如下：[參考labuladong的算法小抄]

int left = 0, right = 0;while(right < s.size())
{//增大窗口window.add(s[right]);right++;while(window needs shrink){//縮小窗口window.remove(s[left]);left++;}
}

主要的細節問題：
1、如何向窗口中添加新元素
2、如何縮小窗口
3、在窗口滑動的哪個階段更新結果

//滑動窗口算法框架
void slidingWindow(string s, string t)
{unordered_map<char,int> need, window;for(char c : t) need[c]++;int left = 0, right = 0;int valid = 0;while(right < s.size()){//c是將要移入窗口的元素char c  = s[right];//右移窗口right++;//進行窗口內數據更新(右移窗口)/*******************//**debug輸出位置***/cout << "window:[ "<<left << " , " << right <<"]"<<endl;/******************///判斷左側窗口是否需要收縮while(window needs shrink){//d是將移出窗口的字符char d = s[left];//左移窗口left++;//進行窗口內數據的一系列更新(左移窗口)}}
}

76. 最小覆蓋子串

https://leetcode-cn.com/problems/minimum-window-substring/
給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 “” 。

注意：如果 s 中存在這樣的子串，我們保證它是唯一的答案。
示例 1：

輸入：s = “ADOBECODEBANC”, t = “ABC”
輸出：“BANC”

示例 2：

輸入：s = “a”, t = “a”
輸出：“a”

提示：
1 <= s.length, t.length <= 10^5
s 和 t 由英文字母組成

滑動窗口

1、初始化window和need兩個哈希表，記錄下窗口中的字符以及需要湊齊的字符：

unordered_map<char,int> need,window;
for(char c : t) need[c]++;

2、使用left和right變量初始化窗口兩端，區間是左閉右開，初始情況下，窗口內是沒有元素的。

int left = 0, right = 0;
while(right < s.size())
{//開始滑動
}

3、定義記錄變量
valid_length表示window內滿足need條件的字符個數，如果valid_length == need.size() 說明窗口已經滿足了條件，已經完全覆蓋了串T。

int valid_length;

在right向右擴充的時候，對新進來的元素進行檢查，如果它是need中的元素，window中對應這個元素就要+1，然后判斷window中這個元素的個數是不是need中這個元素的個數相同，如果相同說明這個元素在window中已經找完了，這時候就需要將valid_length+1了
4、套用模板
確定四個問題的具體細節：
1、當right移動，擴大window，應該更新哪些數據？

更新window計數器

2、當left移動，縮小window，應該更新哪些數據？

更新window計數器

3、什么條件下暫停擴大window，開始移動left縮小window？

當valid長度等于need大小時，應該收縮窗口

4、結果應該在擴大窗口時還是縮小窗口時進行？

縮小窗口的時候進行更新結果

代碼以及注釋

class Solution {
public:string minWindow(string s, string t) {unordered_map<char,int> window,need;//記錄下t中有哪些元素以及每個元素的個數for(char c : t) need[c]++;//初始化窗口邊界int right = 0, left = 0;//window滿足need條件的元素個數int valid_length = 0;//結果字符串在s中的起始地址以及長度，這樣就不要每次更新整個string了int start = 0 , length = INT_MAX;while(right < s.size()){//******************擴充窗口**************//擴充窗口right++;//擴充進來的新元素char c = s[right - 1]; //判斷該元素是否是need中元素if(need.count(c)){window[c]++;if(window[c] == need[c]) valid_length++;}//*******************縮小窗口*************//如果need中所有元素都在window內，并且每個元素的頻數也與window內元素頻數相同，那么此時就得到了一個答案，記錄答案，然后縮小窗口，以獲得更優的答案while(valid_length == need.size()){//如果此次答案比上次的答案長度要小，我們才更新答案if(right - left < length){start = left;length = right - left;}//左邊界向左移動left++;//d是剛移出窗口的元素char d = s[left - 1];//如果need中出現了dif(need.count(d)){//如果之前d元素在window和need出現的頻數相同if(window[d] == need[d]){//刪除了之后，頻數不相同了，所以這個元素也就不滿足了。valid_length--;}window[d]--;}}}//如果length沒有更新，說明s不存在t中字符或者不滿足字符頻數，返回空字符串，否則，使用substr將子串返回return length == INT_MAX ? "" : s.substr(start,length);}
};

567. 字符串的排列

https://leetcode-cn.com/problems/permutation-in-string/
給定兩個字符串 s1 和 s2，寫一個函數來判斷 s2 是否包含 s1 的排列。

換句話說，第一個字符串的排列之一是第二個字符串的子串。

示例1:

輸入: s1 = “ab” s2 = “eidbaooo”
輸出: True
解釋: s2 包含 s1 的排列之一 (“ba”).

示例2:

輸入: s1= “ab” s2 = “eidboaoo”
輸出: False

注意：

輸入的字符串只包含小寫字母
兩個字符串的長度都在 [1, 10,000] 之間

滑動窗口

精確化題目為：假設給你一個S和T，請問S中是否存在一個子串，包含T中所有字符且不包含其他字符
精確化本題細節：
1、移動left縮小窗口的時機:窗口大小大于t的大小，因為各種排列的長度應該是一樣的。
2、當valid_length == need.size()時，說明窗口中的數據是一個合法的數據，應該立即返回true；

class Solution {
public:bool checkInclusion(string s1, string s2) {unordered_map<char,int> window,need;for(char c : s1) need[c]++;int left = 0,right = 0;int valid_length = 0;while(right < s2.size()){//擴充windowright++;char c = s2[right - 1];if(need.count(c)){window[c]++;if(window[c] == need[c]) valid_length++;}//縮小windowwhile(right - left >= s1.size()){if(valid_length == need.size()) return true;left++;char d = s2[left - 1];if(need.count(d)){if(window[d] == need[d]) valid_length--;window[d]--;}}}return false;}
};

438. 找到字符串中所有字母異位詞

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
給定一個字符串 s 和一個非空字符串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。

字符串只包含小寫英文字母，并且字符串 s 和 p 的長度都不超過 20100。

說明：
字母異位詞指字母相同，但排列不同的字符串。
不考慮答案輸出的順序。
示例 1:

輸入:
s: “cbaebabacd” p: “abc”
輸出:
[0, 6]
解釋:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母異位詞。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母異位詞。

** 示例 2:**

輸入:
s: “abab” p: “ab”
輸出:
[0, 1, 2]
解釋:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母異位詞。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母異位詞。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母異位詞。

直接套模板

class Solution {
public:vector<int> findAnagrams(string s, string p) {if(s.empty()) return {};vector<int> result;unordered_map<char,int> need,window;for(char c : p) need[c]++;int left = 0,right = 0;int valid_length = 0;while(right < s.size()){//expand windowright++;char c = s[right - 1];if(need.count(c)){window[c]++;if(window[c] == need[c]){valid_length++;}}//shrink windowwhile(right - left >= p.size()){if(valid_length == need.size()){result.emplace_back(left);}left++;char d = s[left - 1];if(need.count(d)){if(window[d] == need[d]){valid_length--;}window[d]--;}}}return result;}
};

3. 無重復字符的最長子串

之前做過，這次用滑動窗口模板做：
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。
示例 1:

輸入: s = “abcabcbb”
輸出: 3
解釋: 因為無重復字符的最長子串是 “abc”，所以其長度為 3。

示例 2:

輸入: s = “bbbbb”
輸出: 1
解釋: 因為無重復字符的最長子串是 “b”，所以其長度為 1。

示例 3:

輸入: s = “pwwkew”
輸出: 3
解釋: 因為無重復字符的最長子串是 “wke”，所以其長度為 3。
請注意，你的答案必須是子串的長度，“pwke” 是一個子序列，不是子串。

示例 4:

輸入: s = “”
輸出: 0

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、數字、符號和空格組成.

化簡框架

將need、valid去除，更新窗口數據只需要更新window計數器。
當window[c]大于1，說明窗口內存在重復字符，不符合條件，就應該移動left縮小窗口。
對于更新結果:更新結果的操作放在收縮窗口之后，因為收縮之后窗口不存在重復字符。

class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.empty()) return 0;int res = 0;unordered_map<char,int> window;int left = 0, right = 0;while(right < s.size()){//expand windowright++;char c = s[right -1];window[c]++;//如果進入窗口的新元素在窗口內有重復元素，就需要移動left//shrink windowwhile(window[c] > 1){left++;window[s[left - 1]]--;}res = max(res,right - left);}return res;}
};