# 滑動窗口（思路 + 模板） # 滑動窗口（Sliding Window） 筆者最早接觸滑動窗口是`滑動窗口協議`，滑動窗口協議（Sliding Window Protocol），屬于 TCP 協議的一種應用，用于網絡數據傳輸時的流量控制，以避免擁塞的發生。 發送方和接收方分別有一個窗口大小 w1 和 w2。窗口大小可能會根據網絡流量的變化而有所不同，但是在更簡單的實現中它們是固定的。窗口大小必須大于零才能進行任何操作。 我們算法中的滑動窗口也是類似，只不過包括的情況更加廣泛。實際上上面的滑動窗口在某一個時刻就是固定窗口大小的滑動窗口，隨著網絡流量等因素改變窗口大小也會隨著改變。接下來我們講下算法中的滑動窗口。 ## 介紹 滑動窗口是一種解決問題的思路和方法，通常用來解決一些連續問題。 比如 LeetCode 的 [209. 長度最小的子數組](https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/209-chang-du-zui-xiao-de-zi-shu-zu-hua-dong-chua-2/)。更多滑動窗口題目見下方`題目列表`。 ## 常見套路 滑動窗口主要用來處理連續問題。比如題目求解“連續子串 xxxx”，“連續子數組 xxxx”，就應該可以想到滑動窗口。能不能解決另說，但是這種敏感性還是要有的。 從類型上說主要有： - 固定窗口大小 - 窗口大小不固定，求解最大的滿足條件的窗口 - 窗口大小不固定，求解最小的滿足條件的窗口（上面的 209 題就屬于這種） 后面兩種我們統稱為`可變窗口`。當然不管是哪種類型基本的思路都是一樣的，不一樣的僅僅是代碼細節。 ### 固定窗口大小 對于固定窗口，我們只需要固定初始化左右指針 l 和 r，分別表示的窗口的左右頂點，并且保證： 1. l 初始化為 0 2. 初始化 r，使得 r - l + 1 等于窗口大小 3. 同時移動 l 和 r 4. 判斷窗口內的連續元素是否滿足題目限定的條件 - 4.1 如果滿足，再判斷是否需要更新最優解，如果需要則更新最優解 - 4.2 如果不滿足，則繼續。  ### 可變窗口大小 對于可變窗口，我們同樣固定初始化左右指針 l 和 r，分別表示的窗口的左右頂點。后面有所不同，我們需要保證： 1. l 和 r 都初始化為 0 2. r 指針移動一步 3. 判斷窗口內的連續元素是否滿足題目限定的條件 - 3.1 如果滿足，再判斷是否需要更新最優解，如果需要則更新最優解。并嘗試通過移動 l 指針縮小窗口大小。循環執行 3.1 - 3.2 如果不滿足，則繼續。 形象地來看的話，就是 r 指針不停向右移動，l 指針僅僅在窗口滿足條件之后才會移動，起到窗口收縮的效果。  ## 模板代碼 ### 偽代碼 ``` <pre class="calibre18">``` 初始化慢指針 = 0 初始化 ans for 快指針 in 可迭代集合 更新窗口內信息 while 窗口內不符合題意 擴展或者收縮窗口 慢指針移動 返回 ans ``` ``` ### 代碼 以下是 209 題目的代碼，使用 Python 編寫，大家意會即可。 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minSubArrayLen</span><span class="hljs-params">(self, s: int, nums: List[int])</span> -> int:</span> l = total = <span class="hljs-params">0</span> ans = len(nums) + <span class="hljs-params">1</span> <span class="hljs-keyword">for</span> r <span class="hljs-keyword">in</span> range(len(nums)): total += nums[r] <span class="hljs-keyword">while</span> total >= s: ans = min(ans, r - l + <span class="hljs-params">1</span>) total -= nums[l] l += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> <span class="hljs-keyword">if</span> ans == len(nums) + <span class="hljs-params">1</span> <span class="hljs-keyword">else</span> ans ``` ``` ## 題目列表（有題解） 以下題目有的信息比較直接，有的題目信息比較隱蔽，需要自己發掘 - [【Python，JavaScript】滑動窗口（3. 無重復字符的最長子串）](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/pythonjavascript-hua-dong-chuang-kou-3-wu-zhong-fu/) - [76. 最小覆蓋子串](https://leetcode-cn.com/problems/minimum-window-substring/solution/python-hua-dong-chuang-kou-76-zui-xiao-fu-gai-zi-c/) - [209. 長度最小的子數組](https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/209-chang-du-zui-xiao-de-zi-shu-zu-hua-dong-chua-2/) - [【Python】滑動窗口（438. 找到字符串中所有字母異位詞）](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/python-hua-dong-chuang-kou-438-zhao-dao-zi-fu-chua/) - [【904. 水果成籃】（Python3）](https://leetcode-cn.com/problems/fruit-into-baskets/solution/904-shui-guo-cheng-lan-python3-by-fe-lucifer/) - [【930. 和相同的二元子數組】（Java，Python）](https://leetcode-cn.com/problems/binary-subarrays-with-sum/solution/930-he-xiang-tong-de-er-yuan-zi-shu-zu-javapython-/) - [【992. K 個不同整數的子數組】滑動窗口（Python）](https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/992-k-ge-bu-tong-zheng-shu-de-zi-shu-zu-hua-dong-c/) - [【1004. 最大連續 1 的個數 III】滑動窗口（Python3）](https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/1004-zui-da-lian-xu-1de-ge-shu-iii-hua-dong-chuang/) - [【1234. 替換子串得到平衡字符串】\[Java/C++/Python\] Sliding Window](https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/javacpython-sliding-window/367697) - [【1248. 統計「優美子數組」】滑動窗口（Python）](https://leetcode-cn.com/problems/count-number-of-nice-subarrays/solution/1248-tong-ji-you-mei-zi-shu-zu-hua-dong-chuang-kou/) ## 擴展閱讀 - [LeetCode Sliding Window Series Discussion](https://leetcode.com/problems/binary-subarrays-with-sum/discuss/186683/)