76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC"
示例 2：
输入：s = "a", t = "a" 输出："a"
题解：滑动窗口
本题使用滑动窗口求解，即两个指针 l 和 r 都是从最左端向最右端移动，且 l 的位置一定在r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环，但是因为 while 循环负责移动 l 指针，且 l 只会从左到右移动一次，因此总时间复杂度仍然是 O(n)。本题使用了长度为 128 的数组来映射字符，也可以用哈希表替代；其中 chars 表示目前每个字符缺少的数量，flag 表示每个字符是否在 T 中存在
代码
class Solution { public: string minWindow(string s, string t) { // 一共就128个字符 chars记录每个字符的数量，flag记录是否存在这个字符 vector<int> chars(128,0); vector<bool> flag(128,false); // 先统计T中拥有的字符情况 for(int i=0;i<t.size();i++) { chars[t[i]]++; flag[t[i]]=true; } int count=0,l=0,min_l=0,min_size=s.size()+1; for(int r=0;r<s.size();r++) { // 如果当前遍历到的字符在t中存在 if(flag[s[r]]) { if(--chars[s[r]]>=0) { count++; } // 如果当前滑动窗口包含了 t 中所有的字符，那么尝试将 l 向左移，在不影响满足条件的情况下获得最短情况 while(count==t.size()) { // 如果当前包含了所有的 t中字符，并且长度小于当前最小，那么重新赋值 if(r-l+1<min_size) { min_size=r-l+1; min_l=l; } if(flag[s[l]]&&++chars[s[l]]>0) { count--; } l++; // l 右移动（不需要担心破坏满足条件，因为上面的判断已经保存了最小的） } } } return min_size>s.size()?"":s.substr(min_l,min_size); } };
