題目-最小覆蓋子串：

給定一個字符串 S 和一個字符串 T，請在 S 中找出包含 T 所有字母的最小子串。

示例：
輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"

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

過程

一開始企圖用itertools來做個簡單的索引笛卡兒積，算法復(fù)雜度略高。到某些很長的s時，本地可以算，但是服務(wù)器判斷計算超時了OTZ。

class Solution:
    def findindex(self,y,s):
        index = []
        for i in range(len(s)):
            if s[i] == y:
                index.append(i) 
        return index
    def minWindow(self, s, t):
        import itertools
        PossiWindow = []
        result = ''
        min = len(s)
        for y in t:
            PossiWindow.append(self.findindex(y,s))
        for y in itertools.product(*(i for i in PossiWindow)) :
            if len(set(y)) != len(y):
                continue
            sy = sorted(y)
            leny = sy[-1]-sy[0]
            if leny < min:
                result = s[sy[0]:sy[-1]+1]
                min = leny
        print(result)

難受，搜了一下場外，看到關(guān)鍵詞“滑動窗口”，sliding window ，適用于將嵌套for循環(huán)在少數(shù)問題中轉(zhuǎn)換為單個for循環(huán)，減少算法復(fù)雜度。用中文翻譯一下就是說對于尋找指定長度或最小的子串這種問題，可以直接搬來改改。
整理思路成：

• 統(tǒng)計t的字符出現(xiàn)數(shù)
• 按順序讀s,直到出現(xiàn)第一組包含t的子串。去掉左邊無用的字符，記錄此時的長度長度m，存result
• 保持長度為m-1的窗口，繼續(xù)按順序讀s，直到下一組包含t的子串。去掉左邊無用的字符，記錄此時的長度m，存result
• 循環(huán)往右讀長度為m-1的窗口,直到m==len(t)或者m長度找不到符合條件的字符串為止。

然后寫成代碼有

class Solution:
    def minWindow(self, s, t):
        tCount = {} #統(tǒng)計t的字符出現(xiàn)數(shù)
        for y in t:
            tCount[y]= t.count(y)  
        flag = len(tCount) #標(biāo)記是否所有字符都滿足條件
        head,m = 0,len(s)
        result = '' 
        for toe in range(len(s)):   #按順序讀s,直到出現(xiàn)第一組包含t的子串。去掉左邊無用的字符，記錄此時的長度長度m，存result
            if s[toe] in tCount:
                tCount[s[toe]] -= 1
                if tCount[s[toe]] == 0: flag -= 1 #有一個字符滿足條件
                while flag == 0 : #所有字符都滿足條件時，去掉左邊多余字符
                    if (toe-head) < m :
                        result = s[head:toe+1]
                        m = toe-head
                    if s[head] in t:
                        tCount[s[head]] += 1
                        if tCount[s[head]] > 0:
                            flag += 1
                    head += 1
        return result

運行結(jié)果

補充練習(xí)-滑動窗口最大值：

為了鞏固剛學(xué)會的滑動窗口，追加一道題。

給定一個數(shù)組 nums，有一個大小為 k 的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。你只可以看到在滑動窗口 k 內(nèi)的數(shù)字。滑動窗口每次只向右移動一位。
返回滑動窗口最大值。

示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]

注意：
你可以假設(shè) k 總是有效的，1 ≤ k ≤ 輸入數(shù)組的大小，且輸入數(shù)組不為空。

進階：
你能在線性時間復(fù)雜度內(nèi)解決此題嗎？

過程：

因為電腦好（），第一反應(yīng)還是直接一輪輪比較……然后被99%的代碼鄙視了。

class Solution:
    def maxSlidingWindow(self, nums, k):
        step = 1
        result = []
        if nums:
            for head in range(len(nums)-k+1):
                m = nums[head]
                while step < k-1:
                    toe = head +step
                    if nums[toe] > m:
                        m = nums[toe]
                    step += 1
                if step == k-1:
                    toe = head +step
                    if nums[toe] > m:
                        m = nums[toe]
                    step = 1
                result.append(m)
        return result

好吧好吧我用window還不行嗎！

class Solution:
    def maxSlidingWindow(self, nums, k):
        window, result = [], [] #window從大到小排列
        if nums:
            for head in range(len(nums)):
                #得到大于num[head]的有序列表
                while window and nums[window[-1]] <= nums[head]: 
                    window.pop(-1)
                window.append(head)
                #滑動時判斷最左值是否是最大的，是則pop
                if head >= k and window[0] == head - k:
                    window.pop(0)
                if head >= k - 1:
                    result.append(nums[window[0]])
        return result

反正我就是中等水平了……

總結(jié)

• 對于尋找指定長度的最值條件，或符合條件的最小子串這種問題，試試滑動窗口，結(jié)合有序列表的pop。
• 數(shù)學(xué)不好的人腦殼疼，電腦好不行嗎？（喂）