题解 | #最小覆盖子串#

由于需要时间复杂度O(n)，所以遍历所有字符串肯定是不行的。所以考虑使用滑动窗口。

具体做法：从0位置开始，右索引每次移动一个步长，当匹配到目标字符之一时，在hashmap中的计数相应加1，并且如果左侧索引处字符计数已经超出要求时或者是非目标字符时，左侧索引可以向右循环移动。这样从左移动到右边就可以找到最小覆盖子串。

代码如下：

class Solution {
  public:
    string minWindow(string S, string T) {
        // 初始化hashmap
        unordered_map<char, int> hs, ht;
        for (auto t : T) {
            hs[t] = 0;
            ht[t]++;
        }
        int cnt = 0; // 满足条件的char的个数
        // 右索引不断向右，左索引
        int left_min = 0, right_min = -1;
        int left = 0, right = 0; //记录匹配串
        for (int i = 0, j = 0; i < S.length(); i++) {
            char cr = S[i];
            if (ht.count(cr) == 1) { // 右字符是目标字符之一
                hs[cr]++;
                if(hs[cr] == ht[cr])cnt++; // 一个目标字符满足了要求
                right = i;

                char cl = S[j];
                while (ht.count(cl) == 0 || hs[cl] > ht[cl]) { // 左侧索引处是非目标字符 或者 是目标字符，并且计数超出目标
                    if (ht.count(cl) == 1) hs[cl]--;
                    j++;
                    cl = S[j];
                }
                left = j;

                if (cnt == ht.size()) { // 找到了一个覆盖子串
                    if (right_min == -1 || right - left < right_min - left_min) { // 第一次找到 或者 新的更短
                        left_min = left;
                        right_min = right;
                    }
                }
            }
        }
        return S.substr(left_min, right_min - left_min + 1);
    }
};