题解 | #最小覆盖子串#

方法：哈希表+双指针

1、使用哈希表记录下字符串T中出现的字符的频次（记为负数）；

2、遍历字符串S，出现T中的字符就把哈希表中的频次加1，知道哈希表中所有字符串T的字符出现的频次都不为负数时，此时字符串包含了T的所有字符；

3、记录下左指针的位置和字符长度，尝试移动左指针缩小窗口；知道遍历完得到最小的长度和对应的左指针位置。

class Solution {
public:
    bool check(unordered_map<char, int> hash, string T) {
        for (int i = 0; i < T.length(); i++) {
            if (hash[T[i]] < 0)
                return false;
        }
        return true;
    }

    string minWindow(string S, string T) {
        unordered_map<char, int> hash;
	  	// 记录T中出现的字符的频次（记为负数）
        for (int i = 0; i < T.length(); i++)
            hash[T[i]]--;

        int start, left, right = 0;
        int count = INT_MAX;
        for ( ; right < S.length(); right++) {
            if (hash.find(S[right]) != hash.end())
                hash[S[right]]++;
			// 当T中的字符全部出现在S中时
            while(check(hash, T)) {
                if (count > right - left + 1) {
                    count = right - left + 1;
                    start = left;
                }
                // 移动左指针缩小窗口
                if (hash.find(S[left]) != hash.end())
                    hash[S[left]]--;
                left++;
            }
        }
        // 此时表示S中没能包含T中的所有字符，输出空字符串
        if (left == 0)
            return "";
        return string(S.begin() + start, S.begin() + start + count);
    }
};