题目描述
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入:S="ADOBECODEBANC",T="ABC"输出:"BANC"说明：
- 如果 S 中不存这样的子串，则返回空字符串 “”。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
解题思路
滑动窗口算法通用思想。（最小覆盖子串，找到字符串中所有字母异位词，无重复字符的最长子串）
滑动窗口算法的思路是这样：
我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。（双指针实现滑动窗口）
我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
一个比较棘手的问题：如何判断 window 即子串 s[left…right] 是否符合要求，是否包含 t 的所有字符呢？
答：可以用两个哈希表当作计数器解决。用一个哈希表 needs 记录字符串 t 中包含的字符及出现次数，用另一个哈希表 window 记录当前「窗口」中包含的字符及出现的次数，如果 window 包含所有 needs 中的键，且这些键对应的值都大于等于needs 中的值，那么就可以知道当前「窗口」符合要求了，可以开始移动 left 指针了。
滑动窗口算法的抽象思想：
intleft=0,right=0;while(right<s.size()){window.add(s[right]);while(valid){window.remove(s[left]);left++;}right++;}参考代码
classSolution{public:stringminWindow(string s,string t){string res="";// 相当于两个计数器unordered_map<char,int>needs;unordered_map<char,int>windows;for(constauto&c:t){needs[c]++;}intstartIdx=-1;// 记录 window 中已经有多少字符符合要求了intmatch=0;// 这个 matchNum 是解决这个问题的关键！！！ 非常的巧妙！！！// 符合条件的子字符串的最短长度intminLen=INT_MAX;// 在 s 中寻找 t 的「最小覆盖子串」intleft=0,right=0;while(right<s.size()){charc1=s[right];if(needs.find(c1)!=needs.end()){// 加入 windowswindows[c1]++;// 字符 c1 的出现次数符合要求了if(windows[c1]==needs[c1]){match++;}}// window 中的字符串已符合 needs 的要求了 => 不断右移left，缩短区间while(match==needs.size()){// 更新结果if(right-left+1<minLen){minLen=right-left+1;startIdx=left;// res = s.substr(left, minLen); // 贼无语，这里有case超过内存限制了（将substr()放到最后即可）。上面思路多绕了个弯子，实在没必要，其实只要掌握我注释掉的思路就好了，更清晰好理解。}charc2=s[left];if(needs.find(c2)!=needs.end()){// 移出 windowswindows[c2]--;// 字符 c2 出现次数不再符合要求if(windows[c2]<needs[c2]){match--;}}left++;}right++;}// return res;returnstartIdx>=0?s.substr(startIdx,minLen):"";}};
