leetcode 76最小覆盖子串

time O(n) spaceO(n) 的方法：

还是借助哈希表，所有字母初始化为0，将t中出现的所有字母次数全都记录在哈希表里；

采用双指针，分别为一个头指针head,和尾指针tail。flag记录当前[head,tail)没有出现的字母的个数；

　　1. flag不为0时，更改s[tail]的哈希值，即h[s[tail]]--;在t中没有出现的字符哈希值会被减为负数，所以如果h[s[tail]]>=0,那么当前值在t中出现过，flag--；最后向右延伸tail，tail++；

　　2. 可知flag为0时，t中所有的字母都已经在[head,tail)中出现，因此可以比较并记录当前结果的起始位置start和长度len，并且尝试从head缩短当前的子串；

　　h[s[head]]++;之后，只有在t中出现的字母哈希值可能大于0，没有出现的一定小于等于0；如果是t中出现的（即 h[s[head]]>0），则令flag++，类似于出栈的操作；最后向右移动head，即head++;

总之是借哈希表，通过双指针和flag，维护一个window，

class Solution {
public:
    string minWindow(string s, string t) {
        //将是否已经出现全部的t作为判断条件，如果没有，则不断的增加尾部;如果已经满足，则增加头部；time O(n),space O(n)
        int ls=s.size(),lt=t.size();
        if( ls == 0 || lt == 0 ) return "";
        vector<int> h(128, 0);
        for(auto c:t)
            h[c]++;
        int head=0,tail=0,start=0,len=INT_MAX;
        int flag=lt;//>0移动末尾，等于0移动head;
        while(head<ls && tail<=ls){
            if(flag){
                if(tail==ls) break;
                h[s[tail]]--;//所有字母都--，那么之后执行++时未出现在t中的字母一定不会超过0；
                if(h[s[tail]]>=0) flag--;
                tail++;
            }else{
                if(tail-head<len){
                    start=head;
                    len=tail-head;
                }
                h[s[head]]++;
                if(h[s[head]]>0) flag++;//对应所有字母都--的操作
                head++;
            }
        }
        return len==INT_MAX? "":s.substr(start,len);
    }
};

下面方法有2个测试样例超时 time O(n2) space O(n)

class Solution {
public:
    string minWindow(string s, string t) {
        //time O(n2) space O(1);
        int len=s.size(),k=t.size();
        int tail=-1,lon=-1;
        string res=s;
        for(int i=k-1;i<len;i++){
            int j=i;
            multiset<int> h(t.begin(),t.end());
            while(j>=0){
                if(h.count(s[j])) h.erase(h.find(s[j]));
                if(h.size()==0){
                    if(lon<0 || lon>i-j+1) {lon=i-j+1;tail=i;}
                    break;
                }
                j--;
            }
        }
        if(tail==-1) return "";
        res=s.substr(tail-lon+1,lon);
        return res;
    }
};