本文始發于個人公衆号：TechFlow，原創不易，求個關注
今天是LeetCode專題的第45篇文章，我們一起來看看LeetCode的76題，最小視窗子串Minimum Window Substring。
這題的官方難度是Hard，通過了也是34.2%，4202人點贊，299人反對。從通過率以及點贊比來看，這題的品質很高，稍稍有些偏難，是以小夥伴們請做好準備，這是一道有點挑戰的問題。
題意和樣例
我們一起來看下題意，這題的題意很短，給定兩個字元串S和T。要求設計一個複雜度為
的算法，在S串當中找到一個子串，能夠包含T串當中的所有字元。要求傳回合法且長度最小的視窗的内容。
注意：
- 如果不存在這樣的視窗，傳回“”。
- 如果視窗存在，題目保證有且隻有一個。
樣例：
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
分析
我們來分析一下這個問題，從題意當中大家應該都能感受到它的難度。因為上來題目當中就限定了我們使用的算法的複雜度必須是
，然而我們周遊字元串的複雜度就已經是
了，也就是說我們不能引入額外的計算開銷，否則一定不滿足題目的要求。
可能有些同學會想到傳說中在
時間内判斷字元串比對的KMP算法，如果你不知道這個算法也沒有關系，因為這個算法并不适用。因為我們要找的不是完全相等的子串的位置，而是找的是字元構成一樣的子串，是以并不能通過引入字元串比對算法來解決。沒有學過KMP算法的同學可以松一口氣了，這題當中并不會引入新的算法。
解題的套路
一般來說當我們面臨一個算法問題的時候，我們常常的思考過程主要有兩種。一種是适配，說白了就是把可能可以用上的算法往問題上套。根據題意先感覺一下，大概會用到什麼樣的算法，然後詳細地推導适配的過程，看看是不是真的适用或者是有什麼坑，或者是會出現什麼新的問題。如果一切OK，能夠推理得通，那麼這個算法就是解。第二種方法是模組化，也就是說從題意入手，對題意進行深入的分析，對問題進行模組化和抽象，找到問題的核心，進而推導出用什麼樣的算法可以解決。
舉個很簡單的例子，一般來說我們的動态規劃算法都是适配。都是我們先感覺或者是猜測出可以使用動态規劃，然後再去找狀态和轉移，最後建立狀态轉移方程。而一些搜尋問題一般是模組化，我們先對問題進行分析，然後找出需要搜尋的解的存在空間，然後設計算法去搜尋和剪枝，最後找到答案。
據說一些***高手這兩種方法是一起使用的，是以才可以那麼快速地找到解。當然我不是***高手，是以這個也隻是我的猜測。這個思考過程非常有用，特别是當我們面試的時候，遇到一個從未見過的問題，如果你什麼套路也沒有，頭腦一片空白或者是苦思冥想不得要領是很常見的事情。當你有了套路之後，你就可以試着慢慢找到答案了。
回到這道題本身，我們剛才已經試過了，拿字元串比對的算法網上套是不行的。在視野裡似乎也沒有其他的算法可以套用，是以我們換一種思路，試試看模組化。
首先我們可以肯定一點，我們需要在周遊的時候找到答案，這樣才可以保證算法的複雜度是
。我們的目标是尋找子串，也就是說我們周遊的過程應該對應一個子串，并且我們有方法可以快速判斷這個子串是否合法。這樣我們才可以做到周遊的同時判斷答案的可行性。進而可以想到這是一個區間維護的問題，區間維護我們經常使用的方法就是two pointers。是以我們可以試試two pointers能否适用。
實際上這道題的正解就是two pointers。
題解
我們維護了一個區間，我們需要判斷區間裡的字元構成，這個很容易想到可以使用dict，維護每一個字元出現的次數。在這個題目當中，我們隻需要考慮覆寫的情況，也就是說字元多了并不會構成非法。是以我們可以維護一個dict，每次讀入一個字元更新它，當dict當中的字元滿足要求的時候，為了使得區間長度盡量短，我們可以試着移動區間的左側，盡量縮短區間的長度。
從區間維護的角度來說，我們每次移動區間右側一個機關，隻有當區間内已經滿足題意的時候才會移動左側。通過移動左側彈出元素來擷取能夠滿足題意的最佳區間。
我們來看下主要的流程代碼：
# 存儲區間内的字元
segement = {}
for i in range(n):
segement[s[i]] += 1
# 當滿足條件的時候移動區間左側
while l <= i and satisified(segment):
# 更新最佳答案
if i - l + 1 < ans_len:
ans_len = i - l + 1
beg, end = l, i + 1
# 彈出元素
segement[s[l]] -= 1
l += 1
到這裡還有一個小問題，就是怎麼樣判斷這個segment是否合法呢？我們可以用一個數字matched來記錄目前已經比對上的字元的數量。當某個字元在segment當中出現的次數和T中的次數相等的時候，matched加一。當matched的數量和T中字元種類的數量相等的時候，就可以認為已經合法了。
我們把所有的邏輯串起來，就可以通過這題了。
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import Counter, defaultdict
# 通過Counter直接擷取T當中的字元構成
counter = Counter(t)
n, m = len(s), len(counter)
l, beg, end = 0, 0, 0
cur = defaultdict(int)
matched = 0
flag = False
# 記錄合法的字元串的長度
ans_len = 0x3f3f3f3f
for i in range(n):
if s[i] not in counter:
continue
cur[s[i]] += 1
# 當數量比對上的時候，matched+1
if cur[s[i]] == counter[s[i]]:
matched += 1
# 如果已經找到了合法的區間，嘗試縮短區間的長度
while l <= i and matched == m:
if i - l + 1 < ans_len:
flag = True
beg, end = l, i+1
ans_len = i - l + 1
# 彈出左側元素
c = s[l]
if c in counter:
cur[c] -= 1
if cur[c] < counter[c]:
matched -= 1
l += 1
return "" if not flag else s[beg: end]
總結
到這裡，這道題就算是解決了。很多同學可能會覺得疑惑，為什麼我們用到了兩重循環，但是它依然還是
的算法呢？
這個是two pointers算法的常見問題，也是老生常談的話題了。我們在分析複雜度的時候，不能隻簡單地看用到了幾層循環，而是要抓住計算的核心。比如在這個問題當中，我們内部的while循環針對的變量是l，l這個變量對于i整體是遞增的。也就是說無論外面這個循環執行多少次，裡面的這個while循環一共最多累加隻能執行n次。那麼，當然這是一個
的算法。
這題總體來說有些難度，特别是一開始的時候可能會覺得沒有頭緒無從下手。這個時候有一個清晰的頭腦以及靠譜的思考鍊非常重要，希望大家都能學到這個其中思維的過程，這樣以後才可以應付更多的算法問題。
如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也友善擷取更多文章。
本文使用 mdnice 排版
![LeetCode 62，從動态規劃想到更好的解法[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)