原文連結：https：//mp。weixin。qq。com/s/Mc0AZrh4631LkNDvZrqxDQ
大家好吖，我是Johngo！
LeetCode 刷題的進展有段時間沒有更新了，過去的一篇文章有過這方面的解釋，今天再來說一下。
迴歸正題：
兩點原因，第一點就是有讀者說過去文章太長，是否可以考慮截取出來，分類討論。這一點我是有考慮的，事實上本身文章已經是一個類別了，比如說動態規劃，整個介紹超過萬字，自我感覺才把一個問題描述的比較清楚。所以，後面考慮再細分，使得想要表述的問題更加調理清楚，可讀性更強。
另外一點原因呢，就是關於文章頁面展示。也是關於一個可讀性的方面，這個是真真切切花了將近一個月搞的一個事情。就是重新打理了一個網站（www。johngo689。com，感覺還是比較漂亮的，每天都要看幾眼、、哈哈）。
這中間還有人問到為什麼域名起這樣的一個名字，還穿插著數字，咱們還是後面有空在說說（later。。。）
今天咱們一起要討論的是關於「字串」的第一塊內容。
字串 - 滑動視窗
今天再把整個的刷題腦圖放出來，前面的已經細化，後面一塊一塊逐漸會整理出來。
可以看在整個大的腦圖當中
「字串 - 滑動視窗」
這一塊。
上面是整個 LeetCode 演算法刷題計劃，圖中只細化了
二叉樹、動態規劃和字串
相關理論分析和題目的講解。所以，沒有加入的同學們可以私信我，即使現在沒有計劃刷題的也可以加入進來，當個看客也不錯，身處網際網路，遲早會用到。
之前說到過，
「字串」這一塊會出 10 篇覆盤總結，今天是第一篇「字串 - 滑動視窗」
。
「字串 - 滑動視窗」這一塊咱們安排了四個問題，準備用這四個問題將滑動視窗的使用以及相關題目討論清楚。
【簡單】滑動視窗數字之和（引例）
【中等】567。字串的排列 https：//leetcode-cn。com/problems/permutation-in-string/
【困難】239。滑動視窗最大值 https：//leetcode-cn。com/problems/sliding-window-maximum/
【中等】3。無重複字元的最長子串 https：//leetcode-cn。com/problems/longest-substring-without-repeating-characters/
滑動視窗-引例
滑動視窗演算法一般是作用在
字串
或者
陣列
上，透過不斷的滑動邏輯視窗，在特定視窗大小內進行計算的過程。
滑動視窗的方式可以降低時間複雜度，從而減短計算的執行時間。
引例：比如說在字串
s=“5189623196”
中，視窗大小
w=5
，找出每個視窗字元子串的和。
普通的計算方式
：每 5 個進行一次求個計算，時間複雜度方面能夠達到
O（N^2）
。
利用視窗的方式
：可很大程度可以減小時間方面的消耗。就拿引例來說，時間複雜度應該是
O（N）
的線性複雜度。
該案例核心思路是：視窗在每一次的滑動前後，中間元素內容沒有改變，僅僅改變的是開頭和結尾元素。
即：
下一視窗內元素之和 = 上一視窗元素和 - 離開視窗元素值 + 新加入視窗元素值
下面分步驟進行討論，將最終結果寫入到
res
中。
步驟一
：直接計算視窗內元素和，res = ［29］
步驟二
：在上一步驟的基礎上，減去離開視窗的元素，加上新加入視窗的元素。
步驟三
：繼續在上一步驟的基礎上，減去離開視窗的元素，加上新加入視窗的元素
相同邏輯繼續執行。。。。
步驟六
：滑動視窗將最後一個元素包含進來
image-202110
上述每一步驟中，將
sum
值都新增到最終的結果變數
res
中。
滑動視窗這樣的思維方式就很巧妙的進行在視窗的不斷移動，進而產生各元素在視窗邊界進進出出，利用這一點，在時間複雜度方面進行了一個很大提升！
程式碼簡單的寫一下，還是利用 Python，也是因為 Python 的話，絕大多數人還是比較熟悉。
class Solution（object）： def sumSlidingWindow（self， s， w）： sum = 0 res = ［］ # 計算第一個視窗數字之和 for item in range（5）： sum += s［item］ res。append（sum） # 後面利用滑動視窗思想進行計算 for item in range（w， len（s））： sum -= s［item-w］ sum += s［item］ res。append（sum） return res
下面咱們用三個 LeetCode 經典案例進一步闡述滑動視窗這類題目。
滑動視窗經典題目
567。字串的排列【中等】
給你兩個字串 s1 和 s2 ，寫一個函式來判斷 s2 是否包含 s1 的排列。如果是，返回 true ；否則，返回 false 。
換句話說，s1 的排列之一是 s2 的 子串 。
輸入：s1 =
“ab”
s2 =
“eidbaooo”
輸出：
true
解釋：s2 包含 s1 的排列之一 （
“ba”
）。
首先，兩個字串的排列，首先可以想到字典，根據字典去比較。
詞典可根據兩個不同字串將給到的字元進行計數，因此，這樣很同容易進行比較。
另外，在遍歷
s2
的時候，使用滑動視窗，該視窗的長度是字串
s1
的長度，遍歷
s2
使得字元不斷的出入，在此過程中比較兩個字典。
整個過程，記
s1
的長度為
size1
，
s2
的長度為
size2
，視窗大小為
size1
，不斷遍歷
s2
，直到
s2
的結尾。
記
s1
的字典為
dict_s1
，記
s1
的字典為
dict_s2
，在遍歷
s2
的過程中，每滑動一次視窗，比較
dict_s1
和
dict_s2
是否相等。
視窗滑動過程中，需要
刪除滑出視窗的元素
以及
新增滑入視窗的元素
。
刪除滑出視窗的元素
：廣義上是從字典
dict_s2
中刪除，注意此處不能直接刪除，因為可能會有重複元素存在，比如：
{‘a’：2}
，所以只能是將 value 值減 1。之後再判斷 value 值為否為 0，如果為 0 了，這個時候就可以直接將該元素從字典中刪除。
新增滑入視窗的元素
：直接將滑入視窗的元素新增進字典中。
下面用幾個圖清晰的一步一步操作：
初始化
s1
對應的字典
dict_s1={‘a’：1，‘b’：1}
①
s2
對應的字典為圖中視窗中的元素
dict_s2={‘e’：1，‘i’：1}
。
最後判斷
dict_s1 ！= dict_s2
② 向右滑動視窗，由於元素
e
的 value 值為 1，直接刪除該元素，加入新元素
d
，此時，
dict_s2={‘i’：1，‘d’：1}
。
最後判斷
dict_s1 ！= dict_s2
③ 繼續向右滑動視窗，由於元素
i
的 value 值為 1，直接刪除該元素，加入新元素
b
，此時，
dict_s2={‘d’：1，‘b’：1}
。
最後判斷
dict_s1 ！= dict_s2
③ 繼續向右滑動視窗，由於元素
d
的 value 值為 1，直接刪除該元素，加入新元素
a
，此時，
dict_s2={‘b’：1，‘a’：1}
。
最後判斷
dict_s1 == dict_s2
，此時可以直接返回
True
。不用在繼續視窗滑動了。
這個題雖然在 LeetCode 中標記為中等，但是用滑動視窗的方式去解決還是非常容易理解的。
下面是 Python 程式碼的實現：
class Solution（object）： def checkInclusion（self， s1， s2）： size1 = len（s1） size2 = len（s2） if size1 > size2： return False dict_s1 = collections。Counter（s1） dict_s2 = collections。Counter（s2［：size1-1］） left = 0 for right in range（size1-1， size2）： # 增加新新增的元素 dict_s2［s2［right］］ += 1 # 判斷如果字典相同，則返回 True if dict_s1 == dict_s2： return True # 刪除左邊剔除的元素（首先需要將左邊元素的 value 值減 1） dict_s2［s2［left］］ -= 1 # value 值為 0 的時候，就可以刪除該元素了 if dict_s2［s2［left］］ == 0： del（dict_s2［s2［left］］） # 視窗整體向右移動一格 left += 1 right += 1 return False
下面再看一個稍微複雜一點的，也是滑動視窗的典型例題。
239。滑動視窗最大值【困難】
給你一個整數陣列 nums，有一個大小為 k 的滑動視窗從陣列的最左側移動到陣列的最右側。你只可以看到在滑動視窗內的 k 個數字。滑動視窗每次只向右移動一位。
返回滑動視窗中的最大值。
輸入：nums = ［1，3，-1，-3，5，3，6，7］， k = 3
輸出：［3，3，5，5，6，7］
解釋：
滑動視窗的位置 最大值
————————- ——-
［1 3 -1］ -3 5 3 6 7 3
1 ［3 -1 -3］ 5 3 6 7 3
1 3 ［-1 -3 5］ 3 6 7 5
1 3 -1 ［-3 5 3］ 6 7 5
1 3 -1 -3 ［5 3 6］ 7 6
1 3 -1 -3 5 ［3 6 7］ 7
滑動視窗最大值是一道典型的滑動視窗的例題。該題被標記為困難，可能就在於
最大值
的判斷，如果使用傳統方式的話，時間複雜度就會很高。
關於
最大值
，可是嘗試使用
優先佇列
去解決，即
構造大頂堆
，也可以使用
雙向佇列
解決問題。
以下用兩種方式都來解決一下。
方法一：優先佇列解決
由於題目要求是選擇視窗內的最大值，因此需要構造了大頂堆，此時得出來隊首元素就是整個佇列的最大值。
注意點
：我們這裡由於採用 Python 的 heapq 庫來實現，而 heapq 庫只能構造小頂堆。
因此，可以換一個思路進行實現，例如列表 ［1，-3，12］：
首先，每個元素的負值都插入到優先佇列中，構造小頂堆，產生的結果是這樣的 ［-12， 3， -1］
然後，將隊首元素去除並且取反，得到的結果是 12。這就是我們想要的結果，取到了其中的最大值。
關於 Python 使用優先佇列的方式，可以檢視這一篇文章【https：//mp。weixin。qq。com/s/94Rnnt7R5_kTfoAW0j-wyQ】，有詳細的使用方式。
首先，初始化一個視窗大小的優先佇列
window
，並且記錄元素（
注意這裡要取反
）以及元素下標，組裝成一個元祖
（-num， index）
。
然後，當不斷向右移動視窗，把新加進來的元素（元祖）加入到優先佇列中。
最後，判斷當前優先佇列中的隊首元素對應的
index
，是否在固定視窗內，如果在，則取值並且取反；否則，刪除隊首元素，繼續判斷。
下面依舊用幾個圖清晰的一步一步操作：
我們用字串為 nums=［12， -3， 1， -1， 9， 5］， k = 3 來進行說明。
初始化
res
用來儲存每個視窗最大值。
① 初始化優先佇列 window=［（-12， 0）， （3， 1）， （-1， 2）］，判斷隊首元素的下標值
value=0
在當前視窗內。
所以，取出隊首元素
-12
，並且取反，
res=［12］
② 優先佇列 window=［（-12， 0）， （-1， 2）， （1， 3）， （3， 1）］，判斷隊首元素的下標值
value=0
不在當前視窗內，彈出隊首元素。
此時，window=［（-12， 0）， （-1， 2）， （1， 3）， （3， 1）］，再判斷此時隊首元素的下標值
value=2
在當前視窗內。
所以，取出隊首元素
-1
，並且取反，
res=［12， 1］
③ 優先佇列 window=［（-9， 4）， （-1， 2）， （3， 1）， （1， 3）］，判斷隊首元素的下標值
value=4
在當前視窗內。
所以，取出隊首元素
-9
，並且取反，
res=［12， 1， 9］
④優先佇列 window=［（-9， 4）， （-5， 5）， （3， 1）， （1， 3）， （-1， 2）］，判斷隊首元素的下標值
value=4
在當前視窗內。
所以，取出隊首元素
-9
，並且取反，
res=［12， 1， 9， 9］
這個時候就都所有取數完成了！
中間關於 Python 的 hepq 庫構造大頂堆有點繞，這點稍微理解下，對於後面的解題幫助特別大。
思路描述完了，再看下程式碼實現：
def maxSlidingWindow（self， nums， k）： size = len（nums） window = ［（-nums［i］， i） for i in range（k）］ heapq。heapify（window） res = ［-window［0］［0］］ for i in range（k， size）： heapq。heappush（window， （-nums［i］， i）） while window［0］［1］ <= i-k： heapq。heappop（window） res。append（-window［0］［0］） return res
感覺描述了一堆，但是程式碼倒是很簡潔。
說完方法一，下面看看方法二。。。
方法二：雙向佇列解決
為什麼要使用雙向佇列呢？在演算法執行過程中，需要兩邊進行入隊和出隊的操作。
大致思路也比較容易：
首先，初始化一個空佇列 queue；
然後，逐個入隊，但當下一個元素入隊時，判斷與隊尾元素大小。如果小於隊尾元素，則入隊。否則，隊尾依次出隊，直到大於要入隊的元素；
最後，判斷隊首元素是否是在視窗內，如果在視窗內，直接取值，否則，隊首元素出隊。
下面依舊用幾個圖清晰的一步一步操作：
① 元素
12
入隊；視窗範圍 ［0， 0］
未形成視窗，不取值；
② 元素
-3
入隊；視窗範圍 ［0， 1］
比隊尾元素
12
小，直接入隊；
未形成視窗，不取值；
③ 元素
1
入隊；視窗範圍 ［0， 2］
比隊尾元素
-3
大，所以，隊尾元素出隊，元素
1
入隊。而且隊首元素
12
下標
0
在視窗內
取隊首元素
12
；
④ 元素
-1
入隊；視窗範圍 ［1， 3］
比隊尾元素
1
小，元素
-1
入隊。隊首元素
12
下標
0
不在視窗內，元素
12
出隊；取隊首元素
1
的下標
2
在視窗內；
取隊首元素
1
；
⑤ 元素
9
入隊；視窗範圍 ［2， 4］
比隊尾元素
-1
和
1
都大，所以，比他小的隊尾元素均出隊，元素
9
入隊。而且隊首元素
9
下標
4
在視窗內
取隊首元素
9
；
⑤ 元素
5
入隊；視窗範圍 ［3， 5］
比隊尾元素
9
小，元素
5
入隊。而且隊首元素
9
下標
4
在視窗內
取隊首元素
9
；
利用雙向佇列的方式也將視窗內最大元素取出來了！
上面是整體的思路，具體到程式碼中，是把進入佇列的元素替換為元素的下標，這樣實現起來更加容易！
看下 Python 程式碼的實現：
class Solution（object）： def maxSlidingWindow1（self， nums， k）： size = len（nums） queue = collections。deque（） res = ［］ for i in range（0， size）： # 新元素進隊，在隊不空的情況下，需要判斷與隊尾元素的大小 while queue and nums［i］ > nums［queue［-1］］： queue。pop（） queue。append（i） # 在已經形成視窗（i+1>=k）的前提下，判斷隊首是否在視窗內 while queue［0］ < i-k+1： queue。popleft（） # 從形成視窗的時刻開始將元素置於結果集 res 中 if i+1 >= k： res。append（nums［queue［0］］） return res
無論是利用優先佇列還是雙向佇列，都需要注意所取的元素是否在當前的視窗內。
3。無重複字元的最長子串【中等】
給定一個字串
s
，請你找出其中不含有重複字元的
最長子串
的長度。
輸入： s =
“abcabcbb”
輸出： 3
解釋： 因為無重複字元的最長子串是
“abc”
，所以其長度為 3。
想要判斷字元是否存在，通常會使用到字典結構來判斷是否存在。
首先，初始化視窗左右端
left=0
和
right=0
，初始化字典
words
用來存放已加入字元的元素（key）和元素下標（value），例如，
words={‘a’：0，‘b’：1，‘c’：2}
然後，
right
指標向右移動，判斷新加入元素是否存在於字典中，如果存在，讓視窗左邊界指向字典對應 value 值的下一個位置，並且更新字典中對應元素的下標值（value）；如果不存在，則加入字典
words
中；
注意點：
中間有可能 left 已經更新到後邊，而新判斷的元素可能在前面，會導致 left 變小，所以需要採用 max 來進行判斷
舉例：abba，執行到第二個 b 的時候，left=2，此時words={‘a’：0，‘b’：2}。後面再判斷最後的 a 的時候，就會使得 left=0+1=1
因此，需要 left = max（words。get（v） + 1， left）
最後，每一步驟記錄最長子串長度。
依舊用幾個圖清晰的一步一步操作：
① left=0， right=0， 加入新元素
‘a’
，words={‘a’：0}， 視窗長度為1
② left=0， right=1， 加入新元素
‘b’
，words={‘a’：0， ‘b’：1}， 視窗長度為2
③ left=0， right=2， 加入新元素
‘c’
，words={‘a’：0， ‘b’：1， ‘c’：2}， 視窗長度為3
④ left=0， right=3， 加入新元素
‘a’
；
發現
a
已經在 words={‘a’：0， ‘b’：1， ‘c’：2} 存在；
則更新 left=max（words。get（‘a’） + 1， left）=1，words={‘a’：3， ‘b’：1， ‘c’：2}
視窗長度為3
⑤ left=1， right=4， 加入新元素
‘b’
；
發現
‘b’
已經在 words={‘a’：3， ‘b’：1， ‘c’：2} 存在；
則更新 left=max（words。get（‘b’） + 1， left）=2，words={‘a’：3， ‘b’：4， ‘c’：2}
視窗長度為3
⑥ left=2， right=5， 加入新元素
‘c’
；
發現
‘c’
已經在 words={‘a’：3， ‘b’：4， ‘c’：2} 存在；
則更新 left=max（words。get（‘c’） + 1， left）=3，words={‘a’：3， ‘b’：4， ‘c’：5}
視窗長度為3
⑦ left=3， right=6， 加入新元素
‘b’
；
發現
b
已經在 words={‘a’：3， ‘b’：4， ‘c’：5} 存在；
則更新 left=max（words。get（‘b’） + 1， left）=5，words={‘a’：3， ‘b’：6， ‘c’：5}
視窗長度為2
⑧ left=5， right=7， 加入新元素
‘b’
；
發現
‘b’
已經在 words={‘a’：3， ‘b’：6， ‘c’：5} 存在；
則更新 left=max（words。get（‘b’） + 1， left）=7，words={‘a’：3， ‘b’：7， ‘c’：5}
視窗長度為1
左右步驟描述完畢！
根據每一步驟記錄的視窗長度，可得到
最長視窗為 3
。
下面就由上述邏輯得到最終的程式碼：
class Solution（object）： def lengthOfLongestSubstring（self， s）： if not s： return 0 left， right = 0， 0 length = 1 words = {} for right， v in enumerate（s）： if s［right］ in words。keys（）： print（words。get（v） + 1， left） left = max（words。get（v） + 1， left） length = max（right-left+1， length） # 將當前值的 value 值覆蓋 words［v］ = right print（words） return length
好了，今天就「字串-滑動視窗」系列覆盤進行了詳細的分享。另外，關於其他滑動視窗問題以後會在其他專題文章中進行總結！
程式碼和本文的文件都在 https：//github。com/xiaozhutec/share_leetcode ， 估計半年時間會把各方面題目都完整的記錄下來，包括完整的程式碼和詳細的文件說明（都是長圖解讀，邏輯的每一步都可幫助清晰理解）。
需要的小夥伴可以自行下載程式碼執行跑起來！方便給個 star 哈。謝過大家！
