優(yōu)質(zhì)博文：IT-BLOG-CN

一、題目

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

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

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

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

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

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

進(jìn)階： 你能設(shè)計(jì)一個(gè)在o(m+n)時(shí)間內(nèi)解決此問(wèn)題的算法嗎？

二、代碼

思想： 我們用滑動(dòng)窗口的思想解決這個(gè)問(wèn)題。在滑動(dòng)窗口類型的問(wèn)題中都會(huì)有兩個(gè)指針，一個(gè)用于「延伸」現(xiàn)有窗口的r指針，和一個(gè)用于「收縮」窗口的l指針。在任意時(shí)刻，只有一個(gè)指針運(yùn)動(dòng)，而另一個(gè)保持靜止。我們?cè)?code>s上滑動(dòng)窗口，通過(guò)移動(dòng)r指針不斷擴(kuò)張窗口。當(dāng)窗口包含t全部所需的字符后，如果能收縮，我們就收縮窗口直到得到最小窗口。

如何判斷當(dāng)前的窗口包含所有t所需的字符呢？我們可以用一個(gè)哈希表表示t中所有的字符以及它們的個(gè)數(shù)，用一個(gè)哈希表動(dòng)態(tài)維護(hù)窗口中所有的字符以及它們的個(gè)數(shù)，如果這個(gè)動(dòng)態(tài)表中包含t的哈希表中的所有字符，并且對(duì)應(yīng)的個(gè)數(shù)都不小于t的哈希表中各個(gè)字符的個(gè)數(shù)，那么當(dāng)前的窗口是「可行」的。

注意：這里t中可能出現(xiàn)重復(fù)的字符，所以我們要記錄字符的個(gè)數(shù)。

優(yōu)化： 如果s=XX?XABCXXXX，t=ABC，那么顯然[XX?XABC]是第一個(gè)得到的「可行」區(qū)間，得到這個(gè)可行區(qū)間后，我們按照「收縮」窗口的原則更新左邊界，得到最小區(qū)間。我們其實(shí)做了一些無(wú)用的操作，就是更新右邊界的時(shí)候「延伸」進(jìn)了很多無(wú)用的X，更新左邊界的時(shí)候「收縮」扔掉了這些無(wú)用的X，做了這么多無(wú)用的操作，只是為了得到短短的ABC。沒(méi)錯(cuò)，其實(shí)在s中，有的字符我們是不關(guān)心的，我們只關(guān)心t中出現(xiàn)的字符，我們可不可以先預(yù)處理s，扔掉那些t中沒(méi)有出現(xiàn)的字符，然后再做滑動(dòng)窗口呢？也許你會(huì)說(shuō)，這樣可能出現(xiàn)XXABXXC的情況，在統(tǒng)計(jì)長(zhǎng)度的時(shí)候可以扔掉前兩個(gè)X，但是不扔掉中間的X，怎樣解決這個(gè)問(wèn)題呢？優(yōu)化后的時(shí)空復(fù)雜度又是多少？這里代碼給出沒(méi)有優(yōu)化的版本。

class Solution {// 1、通過(guò) hashMap 記錄 t 中的字符串和個(gè)數(shù)// 2、通過(guò) fast slow 快慢指針記錄最短字符串的位置// 3、通過(guò) hashMap 記錄當(dāng)前符合要求的字符串和個(gè)數(shù)Map<Character, Integer> ori = new HashMap();// 定義一個(gè)變量，保存字串的大小，并將符合要求的字串fast/slow指針賦值給resL,resRint fast = 0, slow = 0, len = Integer.MAX_VALUE, resL = -1, resR = -1;Map<Character, Integer> cur = new HashMap();public String minWindow(String s, String t) {// 4、將需要判斷的字串維護(hù)在hashMap中for (int i = 0; i < t.length(); i++) {ori.put(t.charAt(i), ori.getOrDefault(t.charAt(i),0) + 1);}// 5、開始遍歷s串，通過(guò)快慢指針while (fast < s.length() && slow <= fast) {// 6、將s逐個(gè)維護(hù)在hashMap中cur.put(s.charAt(fast), cur.getOrDefault(s.charAt(fast), 0) + 1);// 7、當(dāng)新加入字符后，需要判斷是否滿足最小字串請(qǐng)求，并且小于之前字串的長(zhǎng)度while (check(t.length())) {// left 還沒(méi)有移動(dòng)，所以下面的判斷不能放在 while循環(huán)中if ((fast - slow + 1) < len) {len = fast - slow + 1;resL = slow;resR = fast + 1;}// 將cur中slow下標(biāo)的串-1cur.put(s.charAt(slow), cur.getOrDefault(s.charAt(slow), 0) -1);++slow;}// 循環(huán)退出條件++fast;}return resL == -1 ? "" : s.substring(resL, resR);}private boolean check(Integer len) {// 如果 fast 小于 t 的長(zhǎng)度，直接返回 falseif (fast < len - 1) {return false;}// 遍歷 ori 或者 curIterator iterator = ori.entrySet().iterator();while (iterator.hasNext()) {// 如果 cur 包含該元素，val >= ori.val 則表示成功，否則失敗；Map.Entry entry = (Map.Entry)iterator.next();Character key = (Character)entry.getKey();Integer val = (Integer)entry.getValue();// 當(dāng)前返回的串的個(gè)數(shù)小于目標(biāo)串t的個(gè)數(shù)，說(shuō)明不符合，直接退出if (cur.getOrDefault(key, 0) < val) {return false;}}return true;}
}

時(shí)間復(fù)雜度： 最壞情況下左右指針對(duì)s的每個(gè)元素各遍歷一遍，哈希表中對(duì)s中的每個(gè)元素各插入、刪除一次，對(duì)t中的元素各插入一次。每次檢查是否可行會(huì)遍歷整個(gè)t的哈希表，哈希表的大小與字符集的大小有關(guān)，設(shè)字符集大小為C，則漸進(jìn)時(shí)間復(fù)雜度為O(C?∣s∣+∣t∣))。
空間復(fù)雜度： 這里用了兩張哈希表作為輔助空間，每張哈希表最多不會(huì)存放超過(guò)字符集大小的鍵值對(duì)，我們?cè)O(shè)字符集大小為C，則漸進(jìn)空間復(fù)雜度為O(C)。