题解 | #最小覆盖子串#

class Solution {
  public:
    string minWindow(string S, string T) {
        int cnt = S.length() + 1;
        //记录目标字符串T的字符个数
        std::unordered_map<char, int> hash; 
        for(int i = 0; i < T.length(); i++)
            //初始化哈希表都为负数，找的时候再加为正
            hash[T[i]] -= 1; 
        int slow = 0, fast = 0;  
        //记录左右区间
        int left = -1, right = -1;  
        for(; fast < S.length(); fast++){
            char c = S[fast];
            //目标字符匹配+1
            if(hash.count(c)) {
              ++hash[c];
            }    
            //没有小于0的说明都覆盖了，缩小窗口
            while(check(hash)){   
                //取最优解
                if(cnt > fast - slow + 1){ 
                    cnt = fast - slow + 1;  
                    left = slow;
                    right = fast;
                }
                char c = S[slow];
                if(hash.count(c))
                    //缩小窗口的时候减1
                    hash[c]--; 
                //窗口缩小
                slow++;      
          }
      }
      return left == -1 ? "" : S.substr(left, right - left + 1);
  }
  private:
    bool check(unordered_map<char, int> &hash) { 
      for (const auto &it : hash) {
          if (it.second < 0)
              return false;
      }
      return true;
  }
};