76. 最小覆蓋子串

問題：

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

注意：

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

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

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

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

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

解決：

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

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

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

步驟二
不斷增加i使滑動(dòng)窗口縮小，因?yàn)槭且笞钚∽执?#xff0c;所以將不必要的元素排除在外，使長度減小，直到碰到一個(gè)必須包含的元素，這個(gè)時(shí)候不能再扔了，再扔就不滿足條件了，記錄此時(shí)滑動(dòng)窗口的長度，并保存最小值

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

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

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