LeetCode 76，一題教會你面試算法時的思考套路

今天是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 排版