5/23刷题

1.最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
思路：
如何判断当前的窗口包含所有t所需的字符呢？我们可以用一个哈希表表示t中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含t的哈希表中的所有字符，并且对应的个数都不小于t的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

class Solution {
public:
    unordered_map <char, int> ori, cnt;//构建两个哈希表，1记录t的字符，2动态记录窗口的字符

    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }//如果cnt中字符的值小于ori中对应字符的值，返回false
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto &c: t) {
            ++ori[c];
        }//哈希表1记录t的字符
        int l = 0, r = -1;//双指针
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }//区间内找到一个相同的字符
            //符合要求的话，计算一下长度
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;//左指针收缩
            }
            //不符合要求，左不动，右右移
        }
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};