题解 | #最小覆盖子串#

用双指针实现滑动窗口法，need存放T中需要查找的字符，window哈希表和valid用于检查need中所有的字符是否已经找到。

函数流程：

1. 右指针向右移动，检查每个字符是否在T中，如果在T中将其放入window里，增加valid长度；
2. 当T中所有字符都被找到时，左指针开始向右收敛并逐步更新start和maxlen，当左指针遇到T中字符时，将window里的字符--，缩短valid长度。
3. 完成遍历时，利用三目运算符输出子串。

#include <functional>
class Solution {
public:
    const int MAXLEN = 100001;
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        unordered_map<char, int> need, window;
        for (char c : T) need[c] ++;
        int left = 0, right = 0;
        int valid = 0;
        int start = 0, maxLen = MAXLEN;
        while (right < S.size()) {
            char c = S[right];
            right ++;
            if (need.count(c)){
                window[c] ++;
                if (window[c] == need[c] ) {
                    valid++;
                }
            }
            while(valid == need.size()) {
                if (right - left < maxLen) {
                    start = left;
                    maxLen = right - left;
                }
                char d = S[left];
                left ++;
                if (need.count(d)){
                    if (window[d] == need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return maxLen == MAXLEN ? "" : S.substr(start, maxLen);
    }
};