领扣 76. 最小覆盖子串

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”

说明：
如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

我的代码 8ms

struct Index_char
{
    int index;
    char c;
    Index_char(){}
    Index_char(int i,char j){index=i;c=j;}
};
class Solution {
public:
    string minWindow(string s, string t) {
        int hash[128]={0};
        int had_match=0;
        queue<Index_char>que;
        int temp_hash[128]={0};
        int min_length=s.size()+2;
        int queue_hash[128]={0};//代表队列有几个字符
        string solution;
        for(int i=0;i<t.size();i++)
            hash[t[i]]++;
        for(int i=0;i<s.size();i++)
        {
            if(temp_hash[s[i]]<hash[s[i]])
            {
                temp_hash[s[i]]++;
                had_match++;
                Index_char temp(i,s[i]);
                que.push(temp);
                queue_hash[s[i]]++;
                if(had_match==t.size())
                {
                    int length=i-que.front().index+1;
                    if(length<min_length)
                    {
                        min_length=length;
                        solution=s.substr(que.front().index,length);
                    }
                    had_match--;
                    temp_hash[que.front().c]--;
                    queue_hash[que.front().c]--;
                    que.pop();
                    while(!que.empty())
                    {
                        char c=que.front().c;
                        if(queue_hash[c]>hash[c])
                        {
                            que.pop();
                            queue_hash[c]--;
                        }
                        else
                            break;
                    }
                }
            }
            else if(temp_hash[s[i]]==hash[s[i]]&&hash[s[i]]!=0)
            {
                Index_char temp(i,s[i]);
                que.push(temp);
                if(que.front().c==s[i])
                {
                    que.pop();
                    while(!que.empty())
                    {
                        char c=que.front().c;
                        if(queue_hash[c]>hash[c])
                        {
                            que.pop();
                            queue_hash[c]--;
                        }
                        else
                            break;
                    }
                }
                else
                    queue_hash[s[i]]++;
            }
        }
        return solution;
    }
};

网上的代码 8ms

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> m(128, 0);
        for (auto c : t) m[c]++;
        int count = t.size(), begin = 0, end = 0, d = INT_MAX, head = 0;
        while (end < s.size()) 
        {
            if (m[s[end]]> 0) 
                count--;
            m[s[end]]-- ;
            end++;
            while (count == 0) 
            {
                if (end - begin < d) 
                {
                    head = begin;
                    d = end - begin; 
                }
                if (m[s[begin]]== 0) 
                    count++;
                m[s[begin]]++;
                begin++;
            }
        }
        return d == INT_MAX ? "" : s.substr(head, d);
    }
};