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

注意：

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

思路一：滑動窗口

char * minWindow(char * s, char * t){int hash[58] = {0};int lenS = strlen(s);int lenT = strlen(t);int min = 0, max = INT_MAX; for (int i = 0; i < lenT; ++i) hash[t[i] - 'A']++;for (int j = 0, i = 0; j < lenS; ++j) {if (hash[s[j] - 'A'] > 0) lenT--;hash[s[j] - 'A']--;while (lenT == 0) { if (j - i + 1 < max - min + 1) {max = j;min = i;}if (++hash[s[i] - 'A'] > 0) lenT++;i++;}}if (max == INT_MAX) return "";char* res = malloc(sizeof(char) * (max - min + 2));int i = 0;while (min <= max) res[i++] = s[min++];res[i] = '\0';return res;
}

時間復雜度O(n^2)，空間復雜度O(n)

分析：

首先建立哈希表，將各個英文字母的數量存放到哈希表中，根據s[i]的字符使哈希表相應位置減一不斷判斷是否為最小子串，最后輸出涵蓋t的子串

總結：

本題考察滑動窗口的應用，將是否為最小子串的判斷編寫清楚即可解決