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

一、題目

給你一個字符串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由英文字母組成

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

二、代碼

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

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

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

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

class Solution {// 1、通過 hashMap 記錄 t 中的字符串和個數(shù)// 2、通過 fast slow 快慢指針記錄最短字符串的位置// 3、通過 hashMap 記錄當(dāng)前符合要求的字符串和個數(shù)Map<Character, Integer> ori = new HashMap();// 定義一個變量，保存字串的大小，并將符合要求的字串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、將需要判斷的字串維護在hashMap中for (int i = 0; i < t.length(); i++) {ori.put(t.charAt(i), ori.getOrDefault(t.charAt(i),0) + 1);}// 5、開始遍歷s串，通過快慢指針while (fast < s.length() && slow <= fast) {// 6、將s逐個維護在hashMap中cur.put(s.charAt(fast), cur.getOrDefault(s.charAt(fast), 0) + 1);// 7、當(dāng)新加入字符后，需要判斷是否滿足最小字串請求，并且小于之前字串的長度while (check(t.length())) {// left 還沒有移動，所以下面的判斷不能放在 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 的長度，直接返回 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)前返回的串的個數(shù)小于目標(biāo)串t的個數(shù)，說明不符合，直接退出if (cur.getOrDefault(key, 0) < val) {return false;}}return true;}
}

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