什么是滑動窗口？

其實就是一個隊列,比如題中的 abcabcbb找出其中不含有重復字符的 最長子串 的長度，進入這個隊列（窗口）為 abc 滿足題目要求，當再進入 a，隊列變成了 abca，這時候不滿足要求。所以，我們要移動這個隊列！

如何移動？我們只要把隊列的左邊的元素移出就行了，直到滿足題目要求！一直維持這樣的隊列，找出隊列出現(xiàn)最長的長度時候，求出解！
;

模板

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:import collectionsres =[]need = collections.Counter(p)window = collections.Counter()valid , left , right = 0 , 0 , 0while right < len(s):c = s[right]right += 1#進行窗口內數(shù)據(jù)的一系列更新，代碼就需要改這里if need[c]:window[c] += 1if window[c] == need[c]:valid += 1#判斷左側窗口是否收縮while right - left >= len(p):# 當窗口符合條件時，把起始索引加入 resif valid == len(need):res.append(left)d = s[left]left += 1#進行窗口內數(shù)據(jù)的一系列更新，代碼就需要改這里if need[d]:if window[d] == need[d]:valid -= 1window[d] -= 1return res

滑動窗口中用到了左右兩個指針，它們移動的思路是：以右指針作為驅動，拖著左指針向前走。右指針每次只移動一步，而左指針在內部 while 循環(huán)中每次可能移動多步。右指針是主動前移，探索未知的新區(qū)域；左指針是被迫移動，負責尋找滿足題意的區(qū)間。

初始化窗口端點L，R，一般L為0，R為1初始化最優(yōu)值while R < len(Array):while R < len(Array):R += 1 #移動右端點if R < len(Array):更新狀態(tài) if 狀態(tài)滿足條件:可選的更新最優(yōu)值的位置break #一旦滿足條件即跳出if R == len(Array): # 若循環(huán)是由于移動到數(shù)組末尾結束，則停止整個程序。因為之后已經(jīng)不再有可能的解breakwhile L < R:更新狀態(tài) # 移動左端點，需要更新狀態(tài)L += 1if 狀態(tài)滿足條件：可選的更新最優(yōu)值的位置else： # 一旦窗口所在區(qū)間不再滿足條件即跳出，去移動右端點break可選的對于L，R端點的后續(xù)處理return 最優(yōu)值

LeetCode-3. 無重復字符的最長子串

給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。示例 1:輸入: "abcabcbb" 輸出: 3 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。 示例 2:輸入: "bbbbb" 輸出: 1 解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。 示例 3:輸入: "pwwkew" 輸出: 3 解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。 class Solution:def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""from collections import defaultdictlookup = defaultdict(int)start = 0 # 記錄當前子串的初始位置end = 0 # end自增遍歷一遍整個字符串max_len = 0 # 之前無重復最長子串counter = 0 # 窗口移動標志while end < len(s):if lookup[s[end]] > 0: # 有重復過的就進入循環(huán)counter += 1lookup[s[end]] += 1end += 1while counter > 0: # 窗口移動if lookup[s[start]] > 1:# 是否是窗口最左邊的字符重復：是的話只移動一次，不是的話一直移動直到重復字符在最左邊counter -= 1lookup[s[start]] -= 1start += 1max_len = max(max_len, end - start)return max_len class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""L, R = 0, -1optim = 0status = set()while R < len(s):while R < len(s):R += 1if R == len(s):breakif s[R] not in status:status.add(s[R])optim = max(optim, R - L + 1)else:breakif R == len(s):breakwhile L < R:if s[L] != s[R]:status.remove(s[L])L += 1else:L += 1breakreturn optim

LeetCode-76. 最小覆蓋子串

給你一個字符串 S、一個字符串 T，請在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"
說明：

如果 S 中不存這樣的子串，則返回空字符串 ""。
如果 S 中存在這樣的子串，我們保證它是唯一的答案。
?

class Solution:def minWindow(self, s: 'str', t: 'str') -> 'str':from collections import defaultdictlookup = defaultdict(int)for c in t:lookup[c] += 1start = 0end = 0min_len = float("inf") # 無窮大counter = len(t) # counter為0時，開始窗口移動res = ""while end < len(s):if lookup[s[end]] > 0: # 可行窗口中出現(xiàn)一次t中字符就就記錄一次counter -= 1 lookup[s[end]] -= 1end += 1while counter == 0: # 移動窗口if min_len > end - start:min_len = end - startres = s[start:end]if lookup[s[start]] == 0: # 行為窗口中最左的字符是t中字符并且只在行為窗口中出現(xiàn)一次就停止移動counter += 1lookup[s[start]] += 1start += 1return resn = Solution() nn = n.minWindow('ABAACBAB', 'ABC') print(nn)

159. 至多包含兩個不同字符的最長子串

class Solution:def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:from collections import defaultdictlookup = defaultdict(int)start = 0end = 0max_len = 0counter = 0while end < len(s):if lookup[s[end]] == 0:counter += 1lookup[s[end]] += 1end +=1while counter > 2:if lookup[s[start]] == 1:counter -= 1lookup[s[start]] -= 1start += 1max_len = max(max_len, end - start)return max_len

340. 至多包含 K 個不同字符的最長子串

class Solution:def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:from collections import defaultdictlookup = defaultdict(int)start = 0end = 0max_len = 0counter = 0while end < len(s):if lookup[s[end]] == 0:counter += 1lookup[s[end]] += 1end += 1while counter > k:if lookup[s[start]] == 1:counter -= 1lookup[s[start]] -= 1start += 1max_len = max(max_len, end - start)return max_len

LeetCode-30. 串聯(lián)所有單詞的子串

class Solution:def findSubstring(self, s, words):from collections import Counterif not s or not words:return []one_word = len(words[0])word_num = len(words)n = len(s)if n < one_word: return []words = Counter(words)res = []for i in range(0, one_word): # 防止單詞截斷的問題cur_cnt = 0 # 窗口中每出現(xiàn)一次單詞就加一，非words中單詞減一left = i # 窗口左指針right = i # 窗口右指針cur_Counter = Counter() # 創(chuàng)建窗口while right + one_word <= n: # 窗口右指針移動遍歷sw = s[right:right + one_word]right += one_word# cur_Counter[w] += 1# cur_cnt += 1if w not in words:left = rightcur_Counter.clear()cur_cnt = 0else:cur_Counter[w] += 1cur_cnt += 1while cur_Counter[w] > words[w]:# 窗口中出現(xiàn)非words中單詞或者words中單詞出現(xiàn)1次以上，需移動窗口左指針，移動到w的位置left_w = s[left:left+one_word]left += one_wordcur_Counter[left_w] -= 1cur_cnt -= 1if cur_cnt == word_num : # words中單詞已在窗口中全部出現(xiàn)res.append(left)return resn = Solution() nn = n.findSubstring("barfoothefoobarman", ["foo","bar"]) print(nn)

LeetCode-209. 長度最小的子數(shù)組

給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組。如果不存在符合條件的連續(xù)子數(shù)組，返回 0。示例: 輸入: s = 7, nums = [2,3,1,2,4,3] 輸出: 2 解釋: 子數(shù)組 [4,3] 是該條件下的長度最小的連續(xù)子數(shù)組。 class Solution:def minSubArrayLen(self, s, nums):if sum(nums) < s:return 0if sum(nums) == s:return len(nums)left = 0right = 0sub_sum = 0length = len(nums)for right, item in enumerate(nums):sub_sum += itemwhile sub_sum >= s:length = min(length, right-left+1)sub_sum -= nums[left]left += 1return length class Solution:def minSubArrayLen(self, s, nums):summation = 0L, R = 0, -1optim = len(nums) + 1while R < len(nums):while R < len(nums):R += 1if R < len(nums):summation += nums[R]if summation >= s:optim = min(optim, R - L + 1)breakif R == len(nums):breakwhile L < R:summation -= nums[L]L += 1if summation >= s:optim = min(optim, R - L + 1)else:breakreturn optim if optim != len(nums) + 1 else 0

Leetcode 1004. 最大連續(xù)1的個數(shù) III

給定一個由若干 0 和 1 組成的數(shù)組 A，我們最多可以將 K 個值從 0 變成 1 。 返回僅包含 1 的最長（連續(xù)）子數(shù)組的長度。示例 1：輸入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 輸出：6 解釋： [1,1,1,0,0,1,1,1,1,1,1] 粗體數(shù)字從 0 翻轉到 1，最長的子數(shù)組長度為 6。示例 2：輸入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 輸出：10 解釋： [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗體數(shù)字從 0 翻轉到 1，最長的子數(shù)組長度為 10。 def longestOnes(A: List[int], K: int) -> int:L, R = 0, -1optim = 0while R < len(A):while R < len(A):R += 1if R == len(A):breakif A[R] == 0:K -= 1if K < 0: #第一次不滿足條件breakelse: #滿足條件時更新最優(yōu)值optim = max(optim, R - L + 1)if R == len(A):breakwhile L < R:if A[L] == 0:K += 1L += 1if K >= 0:breakreturn optim

?

滑動窗口問題

3. 無重復字符的最長子串

30. 串聯(lián)所有單詞的子串

76. 最小覆蓋子串

159. 至多包含兩個不同字符的最長子串

209. 長度最小的子數(shù)組

239. 滑動窗口最大值

567. 字符串的排列

632. 最小區(qū)間

727. 最小窗口子序列

總結

以上是生活随笔為你收集整理的LeetCode Hot100 ---- 滑动窗口专题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。