leetcode-python-數組中滑動窗口（一）

leetcode-python-數組中滑動窗口（一）

來自專欄 leetcode-python6 人贊了文章

專題概述

本專題將講解的題目為leetcode中3, 76, 209, 438四道題，主要講解滑動窗口在數組中的應用。文(一)將介紹以及入門滑動窗口，文(二)將使用滑動窗口+哈希表。

目錄

滑動窗口（一）

滑動窗口（二）

代碼相關

1. 所有代碼在leetcode英文網站上都通過了測試。
2. github地址，歡迎star。本專題代碼在code/window-in-array中。

dyq666/leetcode-python?

github.com

1. 如果覺得本文對你有幫助，可以收藏點贊，若文中有問題可在評論區留言

---

本文的內容

先介紹下什麼是滑動窗口，通過兩道很簡單的題目使用滑動窗口，並總結滑動窗口使用的套路。

什麼是滑動窗口？

1. 舉個例子：[1, 7, 5, 6, 7, 8]在這個數組中找到相鄰的任意個數使和為13，求其中符合題意最短的個數。通過肉眼發現目前符合題意的有[1,7,5]和[6,7]。
2. 使用暴力的循環，可以解決問題，但是時間複雜度變為了O(n)
3. 這是我們就需要使用滑動窗口，我們設定一個窗口在數組上面從左往右滾動，初始情況下窗口的大小為[0,0)，一個元素都沒有，我們檢查窗口中元素的和是否小於13，當前是0所以小於13，我們就需要將窗口變大，變為[0,1)，也就是把窗口的右邊界往右推，讓他吃進第0個元素1，現在1仍然小於13，繼續推動右邊界，[0,2)和8，[0,3)和為13，現在和等於13了，我們記下當前的長度。然後將左邊界向右推動，因為我們要尋找最短的長度，只有將左邊界向右推才能使長度更短，按照步驟執行，當窗口推到最右邊，窗口長度又變為0時，本次推動結束
4. 滑動窗口的局限性在於只適用於求連續問題，但是好處是可以大幅度降低時間複雜度。

現在開始真題實戰！

leetcode-003. 無重複字元的最長子串

給定一個字元串，找出不含有重複字元的最長子串的長度。

示例：

給定 "abcabcbb" ，沒有重複字元的最長子串是 "abc" ，那麼長度就是3。

給定 "bbbbb" ，最長的子串就是 "b" ，長度是1。

給定 "pwwkew" ，最長子串是 "wke" ，長度是3。請注意答案必須是一個子串，"pwke" 是 子序列 而不是子串。

問題分析：

我們維護一個滑動窗口，當下一個元素與窗口中的元素沒有重複時，則推動窗口右邊界，使窗口吃進該元素，如果下一個元素與窗口中的元素有重複，則推動左邊界，使窗口縮小的沒有這個元素的大小，然後右窗口又會向右移動吃掉它。每次移動後，我們都記錄當前窗口的大小，最後選一個最長的窗口

代碼部分：

1.初始化窗口的範圍

本專題都會使用左閉右閉的窗口，初始值是[0, -1]代表當前窗口沒有元素。

left, right = 0, -1 # [left...right]

2. 終止條件

在最終時刻左邊界推到末端，右邊界也推到末端。但是右邊界會比左邊界先推到末端，所以判斷中只需要判斷左邊界即可。也就是左邊界必須是在字元串範圍內的

while left < len(s):

3. 移動條件

移動條件我們在題目分析中基本的講到了，現在簡化一下。判斷窗口右邊的值是否在窗口中，是左邊界右移動，不是右邊界右移動。需要注意的是：我們在移動右邊界時多加了一個條件，因為後面要使用s[right + 1]，當需要使用下標獲取值是，一定要保證該下標是合法的。

# 終止條件while left < len(s): # 移動條件 if right + 1 < len(s) and s[right + 1] not in s[left:right + 1]: right += 1 else: left -= 1

4. 記錄結果

在每次移動後我們都取當前窗口與之前存儲的最大窗口的大小中大的一個。而當前窗口大小為右邊界減去左邊界+1，時刻記住我們維護的是一個左閉右閉的區間。

max_len = 0# 終止條件while left < len(s): if right + 1 < len(s) and s[right + 1] not in s[left:right + 1]: right += 1 else: left += 1 max_len = max(max_len, right - left + 1)return max_len

5.最終代碼

left, right = 0, -1 # [left...right]max_len = 0# 終止條件while left < len(s): if right + 1 < len(s) and s[right + 1] not in s[left:right + 1]: right += 1 else: left += 1 max_len = max(max_len, right - left + 1)return max_len

6.優化部分

可跳過此部分先練習下一道題。這部分並不會詳細介紹，只會提供思路具體代碼請參照github。優化（一）：使用in這個操作遍歷字元串可能會影響到效率，使用set代替，也就是每次右窗口動，把吃進的值加到set中，左窗口動把左值從窗口中移除。優化（二）：每次遍歷字元串時，找到窗口中重複元素的位置。也就是不使用in這種遍歷字元串的方式，而使用字元串的find方法，該方法在找不到值是會返回-1。然後判斷這個值如果是-1讓右邊界與移動，否則讓左邊界直接等於該值+1，也就是讓窗口直接來到下一次可以右移的地方，而不是之前的讓左邊界慢慢的移動到這種情況。

209.長度最小的子數組

給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和≥ s的長度最小的子數組。如果不存在符合條件的子數組，返回 0。

示例：

[2, 3, 1, 2, 4, 3], s = 7

結果2。

[4, 3]是長度最小的

問題分析：

按照上題的思路進行如下分析，結合下面的代碼部分，我將每一部分的名字都標註在代碼上了。

1. 窗口範圍：左閉右閉。初始值為[0, -1]。與上題相同。

2. 輔助變數：

（1）滑動窗口中的sum，初始值為0。記錄了當前窗口中元素的值的和，用於與題目中要求的值進行比較

（2）符合條件的滑動窗口的最小值，初始值None，如果遍歷完了還是None則返回0。初始為None的原因是，由於需要找最小值，初始為0肯定是不行的，因為0總是最小的，當然也可以初始為總長度+1。

window_sum = 0min_len = None

3. 終止條件：左邊界推到末端，右邊界也推到末端。但是右邊界會比左邊界先推到末端，所以判斷中只需要判斷左邊界即可。與上題相同。

4. 滑動條件：滑動窗口中的sum小於s，則右邊界右移，將吃進的值加到window_sum中，否則左邊界右移動，從window_sum中減去該值。

5. 改變結果：滑動窗口中的sum大於等於s，並且當前的滑動窗口是最短長度。

6. 返回結果：如果還是None則返回0

代碼部分：

# 滑動窗口範圍l, r = 0, -1# 輔助變數window_sum = 0min_len = None# 終止條件while l < len(nums): # 滑動條件 if window_sum < s and r + 1 < len(nums): window_sum += nums[r + 1] r += 1 else: window_sum -= nums[l] l += 1 # 改變結果 if window_sum >= s: min_len = min(min_len, r - l + 1) if min_len is not None else r - l + 1# 返回結果return min_len if min_len is not None else 0

總結

第二題的思路是滑動窗口的核心，之後的問題都將圍繞第二題的思路展開。步驟1窗口範圍和步驟3的終止條件大部分是不變的，在文(二)中將不會提及

推薦閱讀：