Leetcode-最小覆盖子串（困难）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

滑动窗口，left和right一起从0出发。
right右移，直到left到right范围内完整包含了t子串的每个字符（isfulll=true）。
此时，left向右收紧，直到isfulll=false，此时[left-1,right]里完整匹配了t，但不能停下，因为它可能不是最短的。
right继续向右移动，isfull满足时再缩紧left，直到right走到尽头。
每次比较[left-1,right]子串长度是不是当前最短的，打擂台，如果是，保存入left_min和right_min。

判断t中所有字符都有匹配的方式是使用哈希表，提前将对应的字符设置为负数，一旦匹配成就+1。

class Solution {
public:
    string minWindow(string s, string t) {
        map<char,int> mymap;
        for(auto i:t)
            mymap[i]--;//负数表示待匹配 
        int left=0,right=0;
        int left_min=0,right_min=-1,min_length=100000;//min存最小子串的开头和结尾，-1是适用空字符串情况
        while(right<s.length()){
            if(mymap.count(s[right]))
                mymap[s[right]]++;//每匹配到一个加1
            if(isfull(mymap)){//right移动到已经全部匹配时，left开始向右收紧
                while(left<=right&&isfull(mymap)){
                    if(mymap.count(s[left]))
                        mymap[s[left]]--;
                    left++;
                }//此时[left-1,right]里完整匹配了t，但不能停下，因为它可能不是最短的
                if(right-left+2<min_length) {
                    min_length=right-left+2;
                    right_min=right;
                    left_min=left-1;
                }
            }
            right++;
        }
        string ans="";
        for(int i=left_min;i<=right_min;i++){
            ans+=s[i];
        }
        return ans;
    }
    //利用哈希表存储t的每个字符是否都已被匹配，设置负数也是因为可能有重复字母
    bool isfull(map<char,int>& mymap){
        for(auto i=mymap.begin();i!=mymap.end();i++)
            if(i->second<0) return false;//如果还有负数存在，说明还有的未被匹配
        return true;
    }
};