題目連結：https://leetcode-cn.com/problems/minimum-window-substring/
題目描述
給你一個字元串 S、一個字元串 T，請在字元串 S 裡面找出：包含 T 所有字母的最小子串。
示例：
輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"
說明：
如果 S 中不存這樣的子串，則傳回空字元串 ""。
如果 S 中存在這樣的子串，我們保證它是唯一的答案。
思路
暴力法
如果采用暴力方法，時間複雜度超過了O（n^3），逾時。。
/*
* 暴力解法
* 逾時
*/
class SolutionI {
public:
string minWindow(string s, string t) {
int minLen = INT_MAX;
string ret;
sort(t.begin(), t.end());
if(s==t) return s;
if(s.size() < t.size()) return ret;
for (int i = 0; i <= s.size() - t.size(); ++i) {
for (int j = i+t.size()-1; j < s.size(); ++j) {
string sub = s.substr(i,j-i+1);
int cnt = 0;
sort(sub.begin(),sub.end());
for (int k = 0; k < sub.size() && cnt < t.size(); ++k) {
if(sub[k] == t[cnt])
cnt ++;
}
if(cnt == t.size()){
if(sub.size() < minLen){
minLen = sub.size();
ret = s.substr(i,j-i+1);
}
}
}
}
return ret;
}
};
2 滑動視窗-雙指針O(n)
滑動視窗算法的思路是這樣：
1、我們在字元串 S 中使用雙指針中的左右指針技巧，初始化 left = right = 0，把索引閉區間 [left, right] 稱為一個「視窗」。
2、我們先不斷地增加 right 指針擴大視窗 [left, right]，直到視窗中的字元串符合要求（包含了 T 中的所有字元）。
3、此時，我們停止增加 right，轉而不斷增加 left 指針縮小視窗 [left, right]，直到視窗中的字元串不再符合要求（不包含 T 中的所有字元了）。同時，每次增加 left，我們都要更新一輪結果。
4、重複第 2 和第 3 步，直到 right 到達字元串 S 的盡頭。
這個思路其實也不難，第 2 步相當于在尋找一個「可行解」，然後第 3 步在優化這個「可行解」，最終找到最優解。左右指針輪流前進，視窗大小增增減減，視窗不斷向右滑動。
下面畫圖了解一下，needs 和 window 相當于計數器，分别記錄 T 中字元出現次數和視窗中的相應字元的出現次數。
初始狀态：
增加 right，直到視窗 [left, right] 包含了 T 中所有字元：
現在開始增加 left，縮小視窗 [left, right]。
直到視窗中的字元串不再符合要求，left 不再繼續移動。
之後重複上述過程，先移動 right，再移動 left…… 直到 right 指針到達字元串 S 的末端，算法結束。
這個算法的時間複雜度是 O(M + N)，M 和 N 分别是字元串 S 和 T 的長度。因為我們先用 for 循環周遊了字元串 T 來初始化 needs，時間 O(N)，之後的兩個 while 循環最多執行 2M 次，時間 O(M)。
注意：雖然嵌套的while有兩層，但是總時間并不是M^2；因為while 執行的次數就是雙指針 left 和 right 走的總路程，最多是 2M。
複雜度分析
- 時間複雜度：O（m+n）
- 空間複雜度：O（n）
/*
* 滑動視窗-雙指針法
* left指針收縮視窗；right指針擴大視窗
* 先找到一個可行視窗，再不斷收縮
* 時間複雜度O(|S|+|T|) 空間複雜度O(|S|+|T|)
*/
class Solution {
public:
string minWindow(string s, string t) {
if(s.empty() || t.empty())
return "";
string ret;
unordered_map<int, int> require; // 建立字典對t的字元進行計數
unordered_map<int, int> window;
for(char c:t)
require[c] ++;
int left = 0, right = 0; // 雙指針
int match = 0; // 記錄window中已經有多少字元符合要求了
int minLen = INT_MAX;
int begin = 0; // 最小子串的起始點
while (right < s.size()){
// 右指針右移加入字元擴大視窗
char c1 = s[right];
if(require.count(c1)){
window[c1] ++;
if(window[c1] == require[c1])
match ++;
}
right ++;
// 左指針右移縮小視窗
while (match == require.size()){
if (right - left < minLen){
begin = left;
minLen = right - left;
}
char c2 = s[left];
if(require.count(c2)){
window[c2] --;
if(window[c2] < require[c2])
match--;
}
left++;
}
}
return minLen == INT_MAX? "" : s.substr(begin, minLen);
}
};