讀完本文党晋，你可以去力扣拿下如下題目：
-----------
鑒于前文 二分搜索框架詳解 的那首《二分搜索升天詞》很受好評(píng)缰犁，并在民間廣為流傳菇用，成為安睡助眠的一劑良方，今天在滑動(dòng)窗口算法框架中廊勃，我再次編寫一首小詩來歌頌滑動(dòng)窗口算法的偉大：
關(guān)于雙指針的快慢指針和左右指針的用法绍撞，可以參見前文 雙指針技巧匯總，本文就解決一類最難掌握的雙指針技巧：滑動(dòng)窗口技巧腺兴。總結(jié)出一套框架廉侧，可以保你閉著眼睛都能寫出正確的解法页响。
說起滑動(dòng)窗口算法，很多讀者都會(huì)頭疼段誊。這個(gè)算法技巧的思路非常簡單闰蚕，就是維護(hù)一個(gè)窗口，不斷滑動(dòng)枕扫，然后更新答案么陪腌。LeetCode 上有起碼 10 道運(yùn)用滑動(dòng)窗口算法的題目辱魁，難度都是中等和困難烟瞧。該算法的大致邏輯如下：
int left = 0, right = 0;
while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 縮小窗口
window.remove(s[left]);
left++;
}
}
這個(gè)算法技巧的時(shí)間復(fù)雜度是 O(N)，比字符串暴力算法要高效得多染簇。
其實(shí)困擾大家的参滴，不是算法的思路，而是各種細(xì)節(jié)問題锻弓。比如說如何向窗口中添加新元素砾赔，如何縮小窗口，在窗口滑動(dòng)的哪個(gè)階段更新結(jié)果。即便你明白了這些細(xì)節(jié)暴心，也容易出 bug妓盲，找 bug 還不知道怎么找，真的挺讓人心煩的专普。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)悯衬，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄檀夹，持續(xù)更新筋粗。建議收藏，按照我的文章順序刷題炸渡，掌握各種算法套路后投再入題海就如魚得水了娜亿。
所以今天我就寫一套滑動(dòng)窗口算法的代碼框架，我連再哪里做輸出 debug 都給你寫好了蚌堵，以后遇到相關(guān)的問題买决，你就默寫出來如下框架然后改三個(gè)地方就行，還不會(huì)出 bug：
/* 滑動(dòng)窗口算法框架 */
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++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
...
/*** debug 輸出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判斷左側(cè)窗口是否要收縮
while (window needs shrink) {
// d 是將移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
...
}
}
}
其中兩處 ... 表示的更新窗口數(shù)據(jù)的地方辰斋，到時(shí)候你直接往里面填就行了策州。
而且，這兩個(gè) ... 處的操作分別是右移和左移窗口更新操作宫仗，等會(huì)你會(huì)發(fā)現(xiàn)它們操作是完全對(duì)稱的够挂。
言歸正傳，下面就直接上四道 LeetCode 原題來套這個(gè)框架藕夫，其中第一道題會(huì)詳細(xì)說明其原理孽糖，后面四道就直接閉眼睛秒殺了。
本文代碼為 C++ 實(shí)現(xiàn)毅贮，不會(huì)用到什么編程方面的奇技淫巧办悟，但是還是簡單介紹一下一些用到的數(shù)據(jù)結(jié)構(gòu)，以免有的讀者因?yàn)檎Z言的細(xì)節(jié)問題阻礙對(duì)算法思想的理解：
unordered_map 就是哈希表（字典）滩褥，它的一個(gè)方法 count(key) 相當(dāng)于 Java 的 containsKey(key) 可以判斷鍵 key 是否存在病蛉。
可以使用方括號(hào)訪問鍵對(duì)應(yīng)的值 map[key]。需要注意的是瑰煎，如果該 key 不存在铺然，C++ 會(huì)自動(dòng)創(chuàng)建這個(gè) key，并把 map[key] 賦值為 0酒甸。
所以代碼中多次出現(xiàn)的 map[key]++ 相當(dāng)于 Java 的 map.put(key, map.getOrDefault(key, 0) + 1)魄健。
一、最小覆蓋子串
LeetCode 76 題插勤，Minimum Window Substring沽瘦，難度 Hard：
就是說要在 S(source) 中找到包含 T(target) 中全部字母的一個(gè)子串革骨，且這個(gè)子串一定是所有可能子串中最短的。
如果我們使用暴力解法析恋，代碼大概是這樣的：
for (int i = 0; i < s.size(); i++)
for (int j = i + 1; j < s.size(); j++)
if s[i:j] 包含 t 的所有字母:
更新答案
思路很直接良哲，但是顯然，這個(gè)算法的復(fù)雜度肯定大于 O(N^2) 了助隧，不好臂外。
滑動(dòng)窗口算法的思路是這樣：
1、我們在字符串 S 中使用雙指針中的左右指針技巧喇颁，初始化 left = right = 0漏健，把索引左閉右開區(qū)間 [left, right) 稱為一個(gè)「窗口」。
2橘霎、我們先不斷地增加 right 指針擴(kuò)大窗口 [left, right)蔫浆，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3姐叁、此時(shí)瓦盛，我們停止增加 right，轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right)外潜，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）原环。同時(shí)，每次增加 left处窥，我們都要更新一輪結(jié)果嘱吗。
4、重復(fù)第 2 和第 3 步滔驾，直到 right 到達(dá)字符串 S 的盡頭谒麦。
這個(gè)思路其實(shí)也不難，第 2 步相當(dāng)于在尋找一個(gè)「可行解」哆致，然后第 3 步在優(yōu)化這個(gè)「可行解」绕德，最終找到最優(yōu)解，也就是最短的覆蓋子串摊阀。左右指針輪流前進(jìn)耻蛇，窗口大小增增減減，窗口不斷向右滑動(dòng)胞此，這就是「滑動(dòng)窗口」這個(gè)名字的來歷臣咖。
下面畫圖理解一下，needs 和 window 相當(dāng)于計(jì)數(shù)器豌鹤，分別記錄 T 中字符出現(xiàn)次數(shù)和「窗口」中的相應(yīng)字符的出現(xiàn)次數(shù)亡哄。
初始狀態(tài)：
增加 right枝缔，直到窗口 [left, right) 包含了 T 中所有字符：
現(xiàn)在開始增加 left布疙，縮小窗口 [left, right)蚊惯。
直到窗口中的字符串不再符合要求，left 不再繼續(xù)移動(dòng)灵临。
之后重復(fù)上述過程截型，先移動(dòng) right，再移動(dòng) left…… 直到 right 指針到達(dá)字符串 S 的末端儒溉，算法結(jié)束宦焦。
如果你能夠理解上述過程，恭喜顿涣，你已經(jīng)完全掌握了滑動(dòng)窗口算法思想波闹。現(xiàn)在我們來看看這個(gè)滑動(dòng)窗口代碼框架怎么用：
首先，初始化 window 和 need 兩個(gè)哈希表涛碑，記錄窗口中的字符和需要湊齊的字符：
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
然后精堕，使用 left 和 right 變量初始化窗口的兩端，不要忘了蒲障，區(qū)間 [left, right) 是左閉右開的歹篓，所以初始情況下窗口沒有包含任何元素：
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// 開始滑動(dòng)
}
其中 valid 變量表示窗口中滿足 need 條件的字符個(gè)數(shù)，如果 valid 和 need.size 的大小相同揉阎，則說明窗口已滿足條件庄撮，已經(jīng)完全覆蓋了串 T。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)毙籽，手把手刷 200 道力扣題目洞斯，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新坑赡。建議收藏巡扇，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了垮衷。
現(xiàn)在開始套模板厅翔，只需要思考以下四個(gè)問題：
1、當(dāng)移動(dòng) right 擴(kuò)大窗口搀突，即加入字符時(shí)刀闷，應(yīng)該更新哪些數(shù)據(jù)？
2仰迁、什么條件下甸昏，窗口應(yīng)該暫停擴(kuò)大，開始移動(dòng) left 縮小窗口徐许？
3施蜜、當(dāng)移動(dòng) left 縮小窗口，即移出字符時(shí)雌隅，應(yīng)該更新哪些數(shù)據(jù)翻默？
4缸沃、我們要的結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新？
如果一個(gè)字符進(jìn)入窗口修械，應(yīng)該增加 window 計(jì)數(shù)器趾牧；如果一個(gè)字符將移出窗口的時(shí)候，應(yīng)該減少 window 計(jì)數(shù)器肯污；當(dāng) valid 滿足 need 時(shí)應(yīng)該收縮窗口翘单；應(yīng)該在收縮窗口的時(shí)候更新最終結(jié)果。
下面是完整代碼：
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
// 記錄最小覆蓋子串的起始索引及長度
int start = 0, len = INT_MAX;
while (right < s.size()) {
// c 是將移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判斷左側(cè)窗口是否要收縮
while (valid == need.size()) {
// 在這里更新最小覆蓋子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是將移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
// 返回最小覆蓋子串
return len == INT_MAX ?
"" : s.substr(start, len);
}
需要注意的是蹦渣，當(dāng)我們發(fā)現(xiàn)某個(gè)字符在 window 的數(shù)量滿足了 need 的需要哄芜，就要更新 valid，表示有一個(gè)字符已經(jīng)滿足要求柬唯。而且忠烛，你能發(fā)現(xiàn)，兩次對(duì)窗口內(nèi)數(shù)據(jù)的更新操作是完全對(duì)稱的权逗。
當(dāng) valid == need.size() 時(shí)美尸，說明 T 中所有字符已經(jīng)被覆蓋，已經(jīng)得到一個(gè)可行的覆蓋子串斟薇，現(xiàn)在應(yīng)該開始收縮窗口了师坎，以便得到「最小覆蓋子串」。
移動(dòng) left 收縮窗口時(shí)，窗口內(nèi)的字符都是可行解，所以應(yīng)該在收縮窗口的階段進(jìn)行最小覆蓋子串的更新冶忱，以便從可行解中找到長度最短的最終結(jié)果。
至此遏乔，應(yīng)該可以完全理解這套框架了，滑動(dòng)窗口算法又不難发笔，就是細(xì)節(jié)問題讓人煩得很盟萨。以后遇到滑動(dòng)窗口算法，你就按照這框架寫代碼了讨，保準(zhǔn)沒有 bug捻激，還省事兒。
下面就直接利用這套框架秒殺幾道題吧前计，你基本上一眼就能看出思路了胞谭。
二、字符串排列
LeetCode 567 題男杈，Permutation in String丈屹，難度 Medium：
注意哦，輸入的 s1 是可以包含重復(fù)字符的伶棒，所以這個(gè)題難度不小旺垒。
這種題目彩库，是明顯的滑動(dòng)窗口算法，相當(dāng)給你一個(gè) S 和一個(gè) T袖牙，請(qǐng)問你 S 中是否存在一個(gè)子串，包含 T 中所有字符且不包含其他字符舅锄？
首先鞭达，先復(fù)制粘貼之前的算法框架代碼，然后明確剛才提出的 4 個(gè)問題皇忿，即可寫出這道題的答案：
// 判斷 s 中是否存在 t 的排列
bool checkInclusion(string t, string s) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
char c = s[right];
right++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判斷左側(cè)窗口是否要收縮
while (right - left >= t.size()) {
// 在這里判斷是否找到了合法的子串
if (valid == need.size())
return true;
char d = s[left];
left++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
// 未找到符合條件的子串
return false;
}
對(duì)于這道題的解法代碼畴蹭，基本上和最小覆蓋子串一模一樣，只需要改變兩個(gè)地方：
1鳍烁、本題移動(dòng) left 縮小窗口的時(shí)機(jī)是窗口大小大于 t.size() 時(shí)叨襟，應(yīng)為排列嘛，顯然長度應(yīng)該是一樣的幔荒。
2糊闽、當(dāng)發(fā)現(xiàn) valid == need.size() 時(shí)，就說明窗口中就是一個(gè)合法的排列爹梁，所以立即返回 true右犹。
至于如何處理窗口的擴(kuò)大和縮小，和最小覆蓋子串完全相同姚垃。
三念链、找所有字母異位詞
這是 LeetCode 第 438 題，F(xiàn)ind All Anagrams in a String积糯，難度 Medium：
呵呵掂墓，這個(gè)所謂的字母異位詞，不就是排列嗎看成，搞個(gè)高端的說法就能糊弄人了嗎君编？相當(dāng)于，輸入一個(gè)串 S川慌，一個(gè)串 T啦粹，找到 S 中所有 T 的排列，返回它們的起始索引窘游。
直接默寫一下框架唠椭，明確剛才講的 4 個(gè)問題，即可秒殺這道題：
vector<int> findAnagrams(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
vector<int> res; // 記錄結(jié)果
while (right < s.size()) {
char c = s[right];
right++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判斷左側(cè)窗口是否要收縮
while (right - left >= t.size()) {
// 當(dāng)窗口符合條件時(shí)忍饰，把起始索引加入 res
if (valid == need.size())
res.push_back(left);
char d = s[left];
left++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
return res;
}
跟尋找字符串的排列一樣贪嫂，只是找到一個(gè)合法異位詞（排列）之后將起始索引加入 res 即可。
四艾蓝、最長無重復(fù)子串
這是 LeetCode 第 3 題力崇，Longest Substring Without Repeating Characters斗塘，難度 Medium：
這個(gè)題終于有了點(diǎn)新意，不是一套框架就出答案亮靴，不過反而更簡單了馍盟，稍微改一改框架就行了：
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> window;
int left = 0, right = 0;
int res = 0; // 記錄結(jié)果
while (right < s.size()) {
char c = s[right];
right++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
window[c]++;
// 判斷左側(cè)窗口是否要收縮
while (window[c] > 1) {
char d = s[left];
left++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
window[d]--;
}
// 在這里更新答案
res = max(res, right - left);
}
return res;
}
這就是變簡單了，連 need 和 valid 都不需要茧吊，而且更新窗口內(nèi)數(shù)據(jù)也只需要簡單的更新計(jì)數(shù)器 window 即可贞岭。
當(dāng) window[c] 值大于 1 時(shí)，說明窗口中存在重復(fù)字符搓侄，不符合條件瞄桨，就該移動(dòng) left 縮小窗口了嘛。
唯一需要注意的是讶踪，在哪里更新結(jié)果 res 呢芯侥？我們要的是最長無重復(fù)子串，哪一個(gè)階段可以保證窗口中的字符串是沒有重復(fù)的呢乳讥？
這里和之前不一樣柱查，要在收縮窗口完成后更新 res，因?yàn)榇翱谑湛s的 while 條件是存在重復(fù)元素云石，換句話說收縮完成后一定保證窗口中沒有重復(fù)嘛物赶。
五、最后總結(jié)
建議背誦并默寫這套框架留晚，順便背誦一下文章開頭的那首詩酵紫。以后就再也不怕子串、子數(shù)組問題了好吧错维。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章奖地，手把手帶刷 200 道力扣題目，建議收藏赋焕！對(duì)應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star参歹，歡迎標(biāo)星！
