leetcode必備算法：聊聊滑動(dòng)窗口
前言
我們刷leetcode的時(shí)候，經(jīng)常會(huì)遇到滑動(dòng)窗口類型題目?；瑒?dòng)窗口問(wèn)題非常經(jīng)典，也很有技巧性，一般大廠也喜歡問(wèn)。今天跟大家一起來(lái)學(xué)習(xí)滑動(dòng)窗口的套路，文章如果有不正確的地方，歡迎大家指出哈，感謝感謝~
什么是滑動(dòng)窗口？ 一道算法題走進(jìn)滑動(dòng)窗口 滑動(dòng)窗口可以用來(lái)解決哪些問(wèn)題? 滑動(dòng)窗口框架套路 leetcode案例分析
什么是滑動(dòng)窗口
滑動(dòng)窗口這個(gè)詞，相信大家耳熟能詳啦。因?yàn)檎f(shuō)到TCP的時(shí)候，經(jīng)常談起滑動(dòng)窗口協(xié)議（Sliding Window Protocol）,它是TCP協(xié)議的一種應(yīng)用，用于網(wǎng)絡(luò)數(shù)據(jù)傳輸時(shí)的流量控制，以避免擁塞的發(fā)生。
TCP頭部有個(gè)字段叫win，也即那個(gè)16位的窗口大小，它告訴對(duì)方本端的TCP接收緩沖區(qū)還能容納多少字節(jié)的數(shù)據(jù)，這樣對(duì)方就可以控制發(fā)送數(shù)據(jù)的速度，從而達(dá)到流量控制的目的。
TCP的滑動(dòng)窗口在某一個(gè)時(shí)刻就是固定窗口大小的滑動(dòng)窗口，隨著網(wǎng)絡(luò)流量等因素改變窗口大小也會(huì)隨著改變。算法中的滑動(dòng)窗口有點(diǎn)類似，就是維護(hù)一個(gè)窗口（隊(duì)列/數(shù)組），不斷滑動(dòng)，然后更新答案?；瑒?dòng)窗口，指的是這樣一類問(wèn)題的求解方法，在數(shù)組上通過(guò)雙指針同向移動(dòng)而解決的一類問(wèn)題。
一個(gè)例子走進(jìn)滑動(dòng)窗口算法
我們來(lái)看一道算法題吧：給定一個(gè)整數(shù)數(shù)組，計(jì)算長(zhǎng)度為k的連續(xù)子數(shù)組的最大總和。
輸入：arr []?=?{100,200,300,400}? k = 2
輸出：700
解釋：300?+ 400?= 700
看到這個(gè)題目，我們馬上想到暴力法去解決了，兩個(gè)for搞定：
???public?int?maxSum(int[]?arry,?int?k)?{
????????int?size?=?arry.length;
????????int?maxSum?=?0;
????????for?(int?i?=?0;?i?????????????int?currentSum?=?0;
????????????for?(int?j?=?0;?j?????????????????currentSum?=?currentSum?+?arry[i?+?j];
????????????}
????????????maxSum?=?Math.max(currentSum,?maxSum);
????????}
????????return?maxSum;
????}
暴力法用了兩個(gè)嵌套的for循環(huán)，時(shí)間復(fù)雜度不理想，為O(k*n); 而滑動(dòng)窗口算法可以解決嵌套循環(huán)問(wèn)題，有效降低時(shí)間復(fù)雜度。
因?yàn)榛瑒?dòng)窗口就是維護(hù)一個(gè)窗口，不斷滑動(dòng)，然后更新答案。 我們用滑動(dòng)窗口算法來(lái)走一波：
當(dāng)k=2時(shí)，
我們可以維護(hù)一個(gè)長(zhǎng)度為2的窗口，初始化第一個(gè)窗口值的總和，并保存起來(lái) 然后窗口不斷向右滑動(dòng)，滑動(dòng)過(guò)程中，與保存的最大值比較，并更新答案。 窗口直到滑到最右邊才結(jié)束。
當(dāng)k=3時(shí)，類似的
我們可以維護(hù)一個(gè)長(zhǎng)度為3的窗口，初始化第一個(gè)窗口值的總和，并保存起來(lái) 然后窗口不斷向右滑動(dòng)，滑動(dòng)過(guò)程中，與保存的最大值比較，并更新答案。 窗口直到滑到最右邊才結(jié)束。
于是，我們就可以寫代碼啦：
???public?int?maxSum1(int[]?arry,?int?k)?{
????????int?size?=?arry.length;
????????if?(size?????????????return?-1;
????????}
????????//初始化第一個(gè)窗口值的總和
????????int?maxSum?=?0;
????????for?(int?i?=?0;?i?????????????maxSum?=?maxSum?+?arry[i];
????????}
????????int?sum?=?maxSum;
????????for?(int?i?=?k;?i?????????????sum?=?sum?+?arry[i]?-?arry[i?-?k];
????????????maxSum?=?Math.max(maxSum,sum);
????????}
????????return?maxSum;
????}
使用了滑動(dòng)窗口，時(shí)間復(fù)雜度，只需要O(n)就可以解決啦。
滑動(dòng)窗口可以解決哪些問(wèn)題
哪些leetcode的題目，我們可以用滑動(dòng)窗口去解決呢？
一般情況，子串問(wèn)題，如什么最小覆蓋子串、長(zhǎng)度最小的子數(shù)組等等，都可以考慮使用滑動(dòng)窗口算法。比較經(jīng)典的滑動(dòng)窗口題目有這些：
無(wú)重復(fù)字符的最長(zhǎng)子串 最小覆蓋子串 串聯(lián)所有單詞的子串 至多包含兩個(gè)不同字符的最長(zhǎng)子串 長(zhǎng)度最小的子數(shù)組 滑動(dòng)窗口最大值 字符串的排列 最小窗口子序列
都是leetcode的原題，大家可以去leetcode官網(wǎng)找找手感哈。
滑動(dòng)窗口框架套路
滑動(dòng)窗口的大致邏輯框架，偽代碼如下：
int?left?=0，right?=?0;
while?(right???//增大窗口
??window.add(s[right]);
??right++;
??
??while?(window?needs?shrink){
????//縮小窗口
????window.remove?(s[left]);
????left?++;
??}
}
基本流程就是醬紫：
首先呢，就是獲取原字符串的長(zhǎng)度。 接著維護(hù)一個(gè)窗口（數(shù)組、哈希、隊(duì)列） 窗口一步一步向右擴(kuò)展 窗口在向右擴(kuò)展滑動(dòng)過(guò)程，需要判斷左邊是否需要縮減 最后比較更新答案
我們用這個(gè)框架，嘗試去解一道leetcode的真題吧。
題目：給定一個(gè)字符串 s ，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。
實(shí)例1：
輸入:?s?=?"abcabcbb"
輸出:?3?
解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"abc"，所以其長(zhǎng)度為 3。
示例 2:
輸入:?s?=?"bbbbb"
輸出:?1
解釋:?因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是?"b"，所以其長(zhǎng)度為 1。
因?yàn)樾枰袛嗍欠翊嬖谥貜?fù)字符，所以，我們用一個(gè)哈希集合（HashSet）來(lái)作為窗口
int?lengthOfLongestSubstring(String?s){
?????//獲取原字符串的長(zhǎng)度
?????int?len?=?s.length();
?????//維護(hù)一個(gè)哈希集合的窗口
?????Set?windows?=?new?HashSet<>();
?????int?left=0,right?=0;
?????int?res?=0;
?????while(right???????char?c?=?s.charAt(right);
???????//窗口右移
???????right++;
???????//判斷是否左邊窗口需要縮減，如果已經(jīng)包含，那就需要縮減
???????while(windows.contains(c)){
??????????windows.remove(s.charAt(left));
???????????left++;
???????}
???????windows.add(c);
???????//比較更新答案
???????res?=?Math.max(res,windows.size());
??????}
?????return?res;
}
leetcode案例分析
我們?cè)賮?lái)看一道leetcode真題，加深一下印象哈。
題目：給你一個(gè)字符串S、一個(gè)字符串T。返回S中涵蓋T所有字符的最小子串。如果S中不存在涵蓋T所有字符的子串，則返回空字符串 "" 。
實(shí)例1：
輸入：s =?"ADOBECODEBANC",?t?=?"ABC"
輸出："BANC"
實(shí)例2：
輸入：s =?"a",?t?=?"a"
輸出："a"
我們還是套用這個(gè)框架流程：
-?首先呢，就是獲取原字符串的長(zhǎng)度。
-?接著維護(hù)一個(gè)窗口（數(shù)組、哈希、隊(duì)列）
-?窗口一步一步向右擴(kuò)展
-?窗口在向右擴(kuò)展滑動(dòng)過(guò)程，需要判斷左邊是否需要縮減
-?最后比較更新答案
獲取原字符串的長(zhǎng)度。
這個(gè)比較簡(jiǎn)單，因?yàn)樵}還是需要有左右指針去遍歷字符串S的。
int?len?=?S.length();
接著維護(hù)一個(gè)窗口（數(shù)組、哈希、隊(duì)列）、右移、左邊縮減
我們可以先定義一個(gè)最小的窗口，長(zhǎng)度為0。定義窗口時(shí)，我們得想下：窗口什么時(shí)候右移，什么時(shí)候左邊縮減，怎么比較更新答案。
最小的窗口什么時(shí)候可以右移呢？因?yàn)轭}目要求涵蓋T的所有子串，所以，窗口一開(kāi)始就可以右移，直到包含T的所有字母
顯然，窗口字符串ADOBEC，是S中涵蓋T所有字符的第一個(gè)子串。但是呢，我們要找的是最小子串，ADOBEC還不一定是最小的。因?yàn)椋?/p>
1.當(dāng)前窗口可能包含一個(gè)滿足題目條件的，更小的子窗口字符串。（可以左邊縮減） 2.窗口還沒(méi)滑到的地方，可能包含一個(gè)滿足條件的，更小的字符串。（可以窗口繼續(xù)右移）
找到第一個(gè)滿足條件的窗口字符串ADOBEC后，為了尋找更小的子窗口字符串。我們可以：
1.左邊縮減，如果縮小的窗口仍然滿足包含T所有字母，那當(dāng)前窗口就可能是最小子串。存儲(chǔ)下來(lái)（就類似于滑動(dòng)窗口框架的更新答案哈），然后繼續(xù)從左縮減窗口。 2.如果縮小窗口不能滿足包含T的所有字母，這時(shí)候就可以停止窗口的左邊縮減，轉(zhuǎn)而向右擴(kuò)大窗口啦。
不斷重復(fù)以上的步驟，把找到滿足條件的窗口保存下來(lái)，比較得出最小的子串。示例滿足條件的最小子串是BANC
這道題的難點(diǎn)，其實(shí)是如何判斷S的子串包含T，我們一起來(lái)看下代碼吧：
class?Solution?{
????public?String?minWindow(String?s,?String?t)?{
????????if?(s.length()?==?0?||?s.length()?????????????return?"";
????????}
????????int?sLen?=?s.length();
????????Map?lookup?=?new?HashMap<>();
?????????
????????for?(int?i?=?0;?i?????????????lookup.put(s.charAt(i),?0);
????????}
????????for?(int?i?=?0;?i?????????????Character?c?=?t.charAt(i);
????????????if?(lookup.containsKey(c))?{
????????????????lookup.put(c,?lookup.get(c)?+?1);
????????????}?else?{
????????????????return?"";
????????????}
????????}
????????int?left?=?0;
????????int?right?=?0;
????????int?minLen?=?Integer.MAX_VALUE;
????????int?tCount?=?t.length();
????????String?result?=?"";
????????while?(right?????????????char?c?=?s.charAt(right);
????????????if?(lookup.get(c)?>?0)?tCount--;
????????????lookup.put(c,?lookup.get(c)?-?1);
????????????//窗口右移
????????????right++;
????????????
????????????//已經(jīng)包含T的所有字母
????????????while?(tCount?==?0)?{
????????????????//比較更新答案
????????????????if?(minLen?>?right?-?left)?{
????????????????????minLen?=?right?-?left;
????????????????????result?=?s.substring(left,?right);
????????????????}
????????????????char?c2?=?s.charAt(left);
????????????????if?(lookup.get(c2)?==?0)?tCount++;
????????????????lookup.put(c2,?lookup.get(c2)?+?1);
????????????????//窗口從左邊縮減
????????????????left++;
????????????}
????????}
????????return?result;
????}
}
leetcode提交結(jié)果如下：
這道題是字節(jié)一面真題，大家可以細(xì)看一下哈，也可以加我微信（tianluoboy1024），一起討論一下。
推薦閱讀：
一周學(xué)完MyBatis源碼，萬(wàn)字總結(jié)
歡迎關(guān)注微信公眾號(hào)：互聯(lián)網(wǎng)全棧架構(gòu)，收取更多有價(jià)值的信息。