76. 最小覆蓋子串

問題：

給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 “” 。

注意：

對于 t 中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。
如果 s 中存在這樣的子串，我們保證它是唯一的答案。

示例 1：輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"
解釋：最小覆蓋子串 "BANC" 包含來自字符串 t 的 'A'、'B' 和 'C'。

示例 2：輸入：s = "a", t = "a"
輸出："a"
解釋：整個字符串 s 是最小覆蓋子串。

示例 3:輸入: s = "a", t = "aa"
輸出: ""
解釋: t 中兩個字符 'a' 均應(yīng)包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。

提示：m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母組成

解決：

核心思想在于窗口滑動，并且在滑動的過程中通過維護(hù)一個字典，代表各個元素還需要的個數(shù)

滑動窗口的思想：
用i,j表示滑動窗口的左邊界和右邊界，通過改變i,j來擴(kuò)展和收縮滑動窗口，可以想象成一個窗口在字符串上游走，當(dāng)這個窗口包含的元素滿足條件，即包含字符串T的所有元素，記錄下這個滑動窗口的長度j-i+1，這些長度中的最小值就是要求的結(jié)果。

步驟一
不斷增加j使滑動窗口增大，直到窗口包含了T的所有元素

步驟二
不斷增加i使滑動窗口縮小，因為是要求最小字串，所以將不必要的元素排除在外，使長度減小，直到碰到一個必須包含的元素，這個時候不能再扔了，再扔就不滿足條件了，記錄此時滑動窗口的長度，并保存最小值

步驟三
讓i再增加一個位置，這個時候滑動窗口肯定不滿足條件了，那么繼續(xù)從步驟一開始執(zhí)行，尋找新的滿足條件的滑動窗口，如此反復(fù)，直到j(luò)超出了字符串S范圍。

用一個字典need來表示當(dāng)前滑動窗口中需要的各元素的數(shù)量，一開始滑動窗口為空，用T中各元素來初始化這個need，當(dāng)滑動窗口擴(kuò)展或者收縮的時候，去維護(hù)這個need字典，例如當(dāng)滑動窗口包含某個元素，我們就讓need中這個元素的數(shù)量減1，代表所需元素減少了1個；當(dāng)滑動窗口移除某個元素，就讓need中這個元素的數(shù)量加1。 記住一點：need始終記錄著當(dāng)前滑動窗口下，我們還需要的元素數(shù)量，我們在改變i,j時，需同步維護(hù)need。 值得注意的是，只要某個元素包含在滑動窗口中，我們就會在need中存儲這個元素的數(shù)量，如果某個元素存儲的是負(fù)數(shù)代表這個元素是多余的。比如當(dāng)need等于{‘A’:-2,‘C’:1}時，表示當(dāng)前滑動窗口中，我們有2個A是多余的，同時還需要1個C。這么做的目的就是為了步驟二中，排除不必要的元素，數(shù)量為負(fù)的就是不必要的元素，而數(shù)量為0表示剛剛好。 回到問題中來，那么如何判斷滑動窗口包含了T的所有元素？結(jié)論就是當(dāng)need中所有元素的數(shù)量都小于等于0時，表示當(dāng)前滑動窗口不再需要任何元素。 優(yōu)化 如果每次判斷滑動窗口是否包含了T的所有元素，都去遍歷need看是否所有元素數(shù)量都小于等于0，這個會耗費O(k)O(k)O(k)的時間復(fù)雜度，k代表字典長度，最壞情況下，k可能等于len(S)。 其實這個是可以避免的，我們可以維護(hù)一個額外的變量needCnt來記錄所需元素的總數(shù)量，當(dāng)我們碰到一個所需元素c，不僅need[c]的數(shù)量減少1，同時needCnt也要減少1，這樣我們通過needCnt就可以知道是否滿足條件，而無需遍歷字典了。 前面也提到過，need記錄了遍歷到的所有元素，而只有need[c]>0大于0時，代表c就是所需元素

func minWindow(s string, t string) string {i:=0 //滑動窗口先摁住左邊界，增加右邊界；有合適的窗口后，再挪動左邊界res:=[]int{0,math.MaxInt32} dict := make(map[string]int) //key是string類型，因為rune太痛苦了for _,j:=range t{dict[string(j)]+=1 }needCnt := len(t) //needCnt可以幫我們快速檢查目前還需要元素的總個數(shù)for j,c := range s{if dict[string(c)]>0{//如果元素在字典中，那就可以讓value減一needCnt -= 1	}dict[string(c)]-=1if needCnt==0{ //該窗口可以匹配成功for{ //將窗口左邊界i向右移動，旨在刪除多余重復(fù)元素h:=s[i]if dict[string(h)]==0{break}dict[string(h)]+=1i+=1}if j-i<res[1]-res[0]{ //維護(hù)res最終結(jié)果res[0],res[1]=i,j}//既然已經(jīng)該窗口計算完畢，那我們就接著i+=1往后面繼續(xù)尋找dict[string(s[i])]+=1 //后續(xù)i+=1會刪掉當(dāng)前左邊界，那我們就需要在字典里+1needCnt+=1i+=1}}if res[1]>len(s){return ""} else{return s[res[0]:res[1]+1]}
}