<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 滑動窗口(思路 + 模板) # 滑動窗口(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 如果不滿足,則繼續。 ![](https://img.kancloud.cn/71/1d/711d4d8b2610643559cf5feb7c073fce_323x473.jpg) ### 可變窗口大小 對于可變窗口,我們同樣固定初始化左右指針 l 和 r,分別表示的窗口的左右頂點。后面有所不同,我們需要保證: 1. l 和 r 都初始化為 0 2. r 指針移動一步 3. 判斷窗口內的連續元素是否滿足題目限定的條件 - 3.1 如果滿足,再判斷是否需要更新最優解,如果需要則更新最優解。并嘗試通過移動 l 指針縮小窗口大小。循環執行 3.1 - 3.2 如果不滿足,則繼續。 形象地來看的話,就是 r 指針不停向右移動,l 指針僅僅在窗口滿足條件之后才會移動,起到窗口收縮的效果。 ![](https://img.kancloud.cn/0f/4b/0f4b9bf17cc417c0cb717c7ee3c95f11_477x473.jpg) ## 模板代碼 ### 偽代碼 ``` <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/)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看