基本認(rèn)識
滑動窗口算法的本質(zhì)是雙指針法中的左右指針法,滑動窗口算法是雙指針法中的左右指針法更為形象的一種表達(dá)方式冕碟。
滑動窗口算法可以用以解決數(shù)組拦惋、字符串的子元素問題。所謂滑動窗口安寺，就像描述的那樣厕妖，可以理解成是一個會滑動的窗口，每次記錄下窗口的狀態(tài)挑庶，再找出符合條件的適合的窗口言秸。它可以將嵌套的循環(huán)問題，更高效的解決迎捺。
基本思想與原理
滑動窗口算法举畸，可以將雙層嵌套的循環(huán)問題，轉(zhuǎn)換為單層遍歷的循環(huán)問題凳枝。使用兩個指針一左一右構(gòu)成一個窗口抄沮，就可以將二維循環(huán)的問題轉(zhuǎn)化成一維循環(huán)一次遍歷，相當(dāng)于通過舊有的計算結(jié)果對搜索空間進(jìn)行剪枝岖瑰，使時間復(fù)雜度從O（n2）降低至O（n）叛买。
適用的問題
滑動窗口算法，可以用來解決一些查找滿足一定條件的連續(xù)區(qū)間的性質(zhì)（長度等）的問題蹋订。
往往類似于“請找到滿足xx的最x的區(qū)間（子串率挣、子數(shù)組等）的xx”這類問題都可以使用該方法進(jìn)行解決。
求解的步驟與模板
滑動窗口算法的解題步驟是這樣（以在字符串S中,找最小的子元素使之包含字符串T為例）：
（1）初始化窗口：
我們在字符串 S 中使用雙指針中的左右指針技巧露戒，初始化 left = right = 0难礼，把索引閉區(qū)間 [left, right] 稱為一個「窗口」。
（2）尋找可行解：
我們先不斷地增加 right 指針擴(kuò)大窗口 [left, right]玫锋，直到窗口中的字符串符合要求（包含了 T 中的所有字符）蛾茉。
（3）優(yōu)化可行解：
此時，我們停止增加 right撩鹿，轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right]谦炬，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同時节沦，每次增加 left键思，我們都要更新一輪結(jié)果。
（4）滑動窗口甫贯，直至一次遍歷結(jié)束：
重復(fù)第 2 和第 3 步吼鳞，直到 right 到達(dá)字符串 S 的盡頭。
這個思路其實也不難理解叫搁，第 2 步相當(dāng)于在尋找一個「可行解」赔桌，然后第 3 步在優(yōu)化這個「可行解」供炎，最終找到最優(yōu)解。左右指針輪流前進(jìn)疾党，窗口大小增增減減音诫，窗口不斷向右滑動。
以上思路是比較形象的滑動窗口問題的解題步驟雪位，這類題通常要尋找比較具體的窗口竭钝。因為滑動窗口算法是雙指針法中的左右指針法更為形象的一種表達(dá)方式，因此有的雙指針法中的左右指針法問題所求解比較抽象雹洗，沒有具體的窗口香罐，這就要求我們結(jié)合實際題目做出分析。
引例部分
最小覆蓋字串問題：
解題思路：
這個題我們可以使用滑動窗口算法时肿，既然是找最小的窗口穴吹，我們就先定義一個最小的窗口，也就是長度為零的窗口嗜侮。
我們比較一下當(dāng)前窗口所在的位置的字母港令，是否為T中的一個字母。很顯然锈颗，A是ABC中的一個字母顷霹，也就是所求的最小子串可能包含當(dāng)前窗口，于是我們將窗口擴(kuò)大击吱，直至其包含T所有字符淋淀。
此時，我們找到了一個能滿足條件的窗口覆醇，為了找到一個更小的的能滿足條件的窗口朵纷，我們從左開始縮小窗口，直至縮小后的窗口無法滿足條件永脓，記錄該窗口的狀態(tài)袍辞，更新結(jié)果數(shù)據(jù)。
之后我們再從右邊開始擴(kuò)大窗口常摧，不斷重復(fù)上面的步驟搅吁，直到窗口滑倒最右邊，且找不到合適的窗口為止落午。結(jié)果數(shù)據(jù)中的窗口狀態(tài)就是我們所求的谎懦。
實戰(zhàn)部分
無重復(fù)字符的最長字串問題：
解題思路：
其實就是一個隊列,比如例題中的 abcabcbb，進(jìn)入這個隊列（窗口）為 abc 滿足題目要求溃斋，當(dāng)再進(jìn)入 a界拦，隊列變成了 abca，這時候不滿足要求梗劫。所以享甸，我們要移動這個窗口截碴！我們只要把隊列的左邊的元素移出就行了，直到滿足題目要求枪萄！一直維持這樣的隊列，不斷更新最長窗口的狀態(tài)猫妙，當(dāng)窗口移動至最右端且無法優(yōu)化時瓷翻，記錄中最長窗口的狀態(tài)即為所求。
下面附上Python3的題解代碼
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
left = 0
lookup = set() #定義為set形式去重
max_len = 0
cur_len = 0
for i in range(len(s)):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len:
max_len = cur_len
lookup.add(s[i])
return max_len
趁熱打鐵 刷題練習(xí)部分（持續(xù)更新）
**以下是LeetCode題庫中一些用到滑動窗口算法（思想）的經(jīng)典例題的題目及解析割坠，有題干齐帚，有題解代碼、有解題思路（持續(xù)更新）：
**
No.3.無重復(fù)字符的最長子串:
https://blog.csdn.net/LanXiu_/article/details/104026241
No.11.盛最多水的容器:
https://blog.csdn.net/LanXiu_/article/details/104085783
NO.15.三數(shù)之和：
https://blog.csdn.net/LanXiu_/article/details/104085783
No.16.最接近的三數(shù)之和:
https://blog.csdn.net/LanXiu_/article/details/104085787
No.18.四數(shù)之和:
https://blog.csdn.net/LanXiu_/article/details/104085787
No.30.串聯(lián)所有單詞的子串:
https://blog.csdn.net/LanXiu_/article/details/104121026
No.42.接雨水:
https://blog.csdn.net/LanXiu_/article/details/104177349
No.75.顏色分類:
https://blog.csdn.net/LanXiu_/article/details/104253545
No.76.最小覆蓋子串:
https://blog.csdn.net/LanXiu_/article/details/104253984
No.88.合并兩個有序數(shù)組:
https://blog.csdn.net/LanXiu_/article/details/104282405
