给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串 ""
- 如果 S 中存在这样的子串，我们保证它是唯一的答案
首先使用一个map统计字符串t中字符出现的次数，使用一个变量total记录字符串t的长度，这个长度将用于判断滑动窗口中是否包含所有t中的字符。使用一个变量min表示满足要求的子串的最小长度，一个变量start表示该子串的起始下标。我们按如下假设遍历s进行处理：
- 当遇到一个t中的字符时，将其map中的计数减1（可能小于0，因为s中可能包含多个）
- 如果减1之前计数大于0，说明这个字符应该含入滑动窗口中，此时total减1
- 如果减1之前计数小于等于0，说明这个字符在s中出现了很多次，此时total不变
- 当遇到一个不在t中出现的字符时，跳过
显然，当total为0时，我们找到了一个满足要求的滑动窗口，这个滑动窗口中，包含了所有t中的字符。因此，我们比较这个滑动窗口的长度与min的值，如果小于min，说明找到了一个新的滑动窗口，因此更新min和start
既然当total为0时，找到了一个满足要求的滑动窗口，那么下一步该怎么做？注意到我们找到的第一个滑动窗口是位于最左边，此时map中一些字符的计数可能小于0，因为t中的某些字符在该滑动窗口中出现了很多次。此时我们从左边开始释放字符，目的是希望在右边能找到一个新的相同字符，从而得到一个新的满足要求的滑动窗口。但是从左边开始，第一个在t中的字符可能是一个冗余的字符（即map中的计数小于0），因此释放了这个字符后，滑动窗口中还是拥有满足条件的字符，那么此时回收应该只增加其在map中的计数，但是不需要从右边开始滑动窗口。因此，只有一个在t中，并且map中计数为0的字符，那么才说明滑动窗口中这个字符的数量“恰好”满足要求，因此可以开始从右边滑动窗口，也就是说，我们还应该从右边找到1个这样字符，使得map中其计数递减后，又变为0。即需要将total加1
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char,int> map;
for(char c : t) map[c]++;
int start = 0,i = 0,min = INT_MAX;
int total = t.length();
for(int j = 0;j < s.length();j++){
if(map.find(s[j]) != map.end())//如果遇到一个t中的字符
if(map[s[j]]-- > 0)
total--;
while(total == 0){//说明当前滑动窗口覆盖了t中的所有字符
if(j - i + 1 < min){
min = j - i + 1;
start = i; //更新start的位置
}
//从滑动窗口左边回收字符，寻找下一个满足条件的滑动窗口
//如果t中某些字符在滑动窗口中出现了多次，对于map中的计数会<0
//如果++没有大于0，说明是遇到一个在滑动窗口中出现多次的字符
//因此不增加total
if(map.find(s[i]) != map.end()){
if(++map[s[i++]] > 0)
total++;
}
else i++;
}
}
return min == INT_MAX ? "" : s.substr(start,min);
}
};