一 滑動窗口
滑動窗口法（sliding window）常用于輸入為數(shù)組，輸出為統(tǒng)計(jì)滿足特定約束條件的子串次數(shù)的情況锻狗。
通常情況下祟同，滑動窗口法可以考慮為暴力雙循環(huán)算法的優(yōu)化，根據(jù)所要求子串的性質(zhì)厢蒜，減少遍歷次數(shù)霞势。具體在實(shí)現(xiàn)過程中，根據(jù)子串所要求的性質(zhì)斑鸦，可以采用數(shù)據(jù)結(jié)構(gòu)來保存窗口的信息愕贡，便于信息的存取，常用的數(shù)據(jù)結(jié)構(gòu)有：
- SortedList (sortedcontainers)
- dict
- list
在滑動窗口解決中巷屿，重要的一步是判斷窗口左端left和窗口右端right的更新條件固以。通常滑動窗口右端right是按照逐步迭代嘱巾，而窗口左端left則在滿足子串約束條件的情況下憨琳，從左到右，或從右到左進(jìn)行遍歷旬昭，相當(dāng)于縮小窗口篙螟。注意l和r均為往右移動，只不過r是一次一步问拘，l是根據(jù)子串性質(zhì)闲擦，可一次多步。
考慮：Leetcode 1100. 長度為 K 的無重復(fù)字符子串
給你一個(gè)字符串 S场梆，找出所有長度為 K 且不含重復(fù)字符的子串墅冷，請你返回全部滿足要求的子串的 數(shù)目。
示例 1：
輸入：S = "havefunonleetcode", K = 5
輸出：6
解釋：
這里有 6 個(gè)滿足題意的子串或油，分別是：'havef','avefu','vefun','efuno','etcod','tcode'寞忿。
示例 2：
輸入：S = "home", K = 5
輸出：0
解釋：
注意：K 可能會大于 S 的長度。在這種情況下顶岸，就無法找到任何長度為 K 的子串腔彰。
解題思路: 考慮從左到右遍歷數(shù)組叫编，Pos記錄某元素出現(xiàn)的位置信息，對于新增元素s[r],若未出現(xiàn)在Pos中霹抛，則窗口右端右移一步并更新Pos搓逾，如果已出現(xiàn)在Pos中，則窗口左端l右移到s[l:r]滿足沒有重復(fù)元素性質(zhì)的位置杯拐，本題中為重復(fù)元素首次出現(xiàn)位置的右邊一步霞篡，如下圖所示。
幻燈片11.jpg
幻燈片12.jpg
幻燈片14.jpg
參考題解：滑動窗口法解決長度為K的無重復(fù)子串問題(含圖文實(shí)例詳解)
class Solution:
def numKLenSubstrNoRepeats(self, S: str, K: int) -> int:
pos = {}
l = r = 0
count = 0
while (r < len(S)):
if S[r] not in pos:
pos[S[r]] = r
else:
# 刪除l到pos[S[r]]的元素信息
start = pos[S[r]] + 1
for i in range(l, pos[S[r]] + 1):
del pos[S[i]]
l = start
pos[S[r]] = r
if len(pos) == K:
count += 1
del pos[S[l]]
l += 1
r += 1
return count
二 滑動窗口解決框架
滑動窗口法重點(diǎn)在于是根據(jù)特定子串的性質(zhì)端逼，來維護(hù)某數(shù)據(jù)結(jié)構(gòu)信息朗兵，以此來減少暴力枚舉的迭代次數(shù)，形象上像窗口右端不斷蠕動顶滩，窗口左端不斷跟進(jìn)的滑動過程余掖。某些情況下，特定子串的性質(zhì)可以用表格記錄礁鲁，因此這時(shí)也可采用動態(tài)規(guī)劃法盐欺。
滑動窗口法代碼大體框架如下：
#滑動窗口解決框架
def solution(nums):
#保存特定信息的數(shù)據(jù)結(jié)構(gòu)
structure = DataStructure()
#窗口左端left和窗口右端right
l = r =0
#滿足約束條件的子串?dāng)?shù)
res = 0
while r<len(nums):
#加入第r個(gè)節(jié)點(diǎn)，更新datastructure的性質(zhì)
structure.add(nums[r])
#nums[r]加入struture后滿足某種條件
if structure.satisfy_condition():
#則更新datastruture的性質(zhì)
structure.update()
#nums[r]不滿足某種條件
else:
#從左到右或從右到左更新窗口左端l仅醇，l根據(jù)子串約束的性質(zhì)找田，
#移動到窗口[l:r]滿足約束性質(zhì)為止。
while not structure.satisfy_condition():
l+=1
structure.remove(nums[l])
#更新滿足約束的子串個(gè)數(shù)
update(res)
#窗口右端往右移動一格
r+=1
return res
三 Leetcode例題
很多習(xí)題可供參考着憨，列出一部分和題解如下：
3 劍指 Offer 57 - II. 和為s的連續(xù)正數(shù)序列 -暴力枚舉法 -函數(shù)解析法 -滑動窗口法 - 參考題解和為s的連續(xù)正數(shù)序列
8 q567. 字符串的排列 -暴力法 -滑動窗口法
12 239. 滑動窗口最大值 -偷懶解法滑動窗口+sortedlist
