滑動窗口可以解決哪些問題唱较？
? 76. 最小覆蓋字串
? 567. 字符串的排列
? ? 438. 找到字符串中所有字母異位詞
? ? 3.無重復(fù)字符的最長子串
? ? ……
這個算法的思路非常簡單召川，維護一個窗口，不斷滑動汉形，然后更新答案倍阐。LeetCode上起碼有10道運用滑動窗口算法的題目，難度都是中等和困難峰搪。大致邏輯如下：
這個算法的時間復(fù)雜度是 O(N)，比字符串暴力算法要高效得多使套。
其實令人困擾的不是算法思路鞠柄，也是各種細(xì)節(jié)問題。
? ? 如何向窗口中添加新元素厌杜？
? ? 如何縮小窗口？
? ? 在窗口滑動的那個階段更新結(jié)果侧馅？
? ? ……
代碼框架
一呐萌、最小覆蓋子串
LeetCode 76, 難度hard：
如果使用暴力解法谊娇，代碼大概如下：
思路很直接，但是這個算法的復(fù)雜度肯定大于 O(N^2) 了赠堵。
滑動窗口的思路是這樣的：
1. 在字符串 S 中使用雙指針中的左右指針技巧法褥，初始化 left = right = 0，把索引左閉右開區(qū)間 [left, right)??稱為一個「窗口」
2. 先不斷地增加 right 指針擴大窗口? [left, right) 半等，直到窗口中的字符串符合要求（包含了 T 中的所有字符）
3. 此時呐萨，停止增加 right, 轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right)莽囤，直到窗口中的 字符串不再符合要求（不包含 T 中的所有字符了）
4. 重復(fù) 第 2 步 和 第 3 步，直到 right 到達字符串 S 的盡頭惨远。
其實這個思路也不難话肖，第 2 步相當(dāng)于在尋找一個「可行解」，第 3 步在優(yōu)化這個「可行解」最筒，最終找到最優(yōu)解。左右指針輪流前進是钥，窗口大小增增減減，窗口不斷向右滑動虏冻，這就是「滑動窗口」這個名字的來歷弹囚。
valid 表示窗口中滿足 need 條件的字符個數(shù)，這里有考慮到某個字符可能有多個蛮穿，當(dāng)發(fā)現(xiàn)某個字符在window的數(shù)量滿足了need的需要毁渗，才會更新valid践磅，表示有一個字符已經(jīng)滿足要求灸异。如果 valid 和 need.size大小相同，則說明窗口已完全覆蓋了串T檐春，可以開始收縮窗口以便得到「最小覆蓋子串」么伯。
移動 left 收縮窗口時，窗口內(nèi)的字符都是可行解，所以應(yīng)該在收縮窗口的階段進行最小覆蓋子串的更新朋贬，以便從可行解中找到長度最短的最終結(jié)果窜骄。
二、字符串排列
LeetCode 567邻遏，難度 Medium
注意，輸入的 s1 是可以包含重復(fù)字符的赎线，所以這個題難度不小糊饱。
這種題目垂寥，是明顯的滑動窗口算法另锋，相當(dāng)于給你一個 S 和 一個 T，問你 S 中是否存在一個子串文判，包含 T 中所有字符且不包含其他字符室梅？
這道題的解法基本上和最小覆蓋子串一摸一樣，只需要改變兩個地方：
????1. 本題移動 left? 縮小窗口的時機是窗口大小大于 t.size() 時亡鼠，因為排列嘛，顯然長度應(yīng)該是一樣的仁热。
? ? 2. 當(dāng)發(fā)現(xiàn) valid == need.size()時浑厚，就說明窗口中是一個合法排列，應(yīng)該立即返回 true钳幅。
三炎滞、找所有字母異位詞
LeetCode 438，難度 Medium
這個所謂的字母異位詞钠导，不就是排列嘛，相當(dāng)于輸入一個串S牡属，一個串 T，找到 S 中所有 T 的排列悴势，返回它們的起始索引措伐。
跟尋找字符串排列一樣，只是找到一個合法異位詞（排列）之后將其實索引加入 res 即可侥加。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
四、最長無重復(fù)子串
LeetCode3昔穴， 難度Medium
這題變簡單了提前，連 need 和 valid 都不需要，更新窗口內(nèi)的數(shù)據(jù)也只需要簡單地更新計數(shù)器 window即可岖研。當(dāng)window[c] 值大于 1 時，說明窗口中存在重復(fù)字符害淤，不符合條件拓售，就該移動 left 縮小窗口了。
唯一需要注意的是础淤，在哪里更新結(jié)果 res 呢？我們要的是最長無重復(fù)子串鸽凶，哪一個階段可以保證窗口中的字符串是沒有重復(fù)的呢？這里和之前不一樣决摧，要在收縮窗口完成之后更新 res ，因為窗口收縮的 while 條件是存在重復(fù)元素掌桩，換句話說收縮完成后一定保證窗口中沒有重復(fù)。
