【LeetCode】76. 最小覆盖子串

• 注意map用法：unordered_map<string, int> differ
• emplace_back()
• 范围循环（range-based for loop）：for (string &word: words)

代码

class Solution {
public:
    unordered_map<char, int> ori, cnt; // 存储字符出现次数的哈希表

    // 检查 cnt 中的字符出现次数是否满足 ori 中的要求
    bool check() {
        for (const auto& p : ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    // 寻找最小窗口子串
    string minWindow(string s, string t) {
        for (const auto& c : t) {
            ++ori[c]; // 统计 t 中每个字符的出现次数
        }

        int l = 0, r = -1; // 滑动窗口的左右指针
        int len = INT_MAX; // 最小窗口子串的长度
        int ansL = -1, ansR = -1; // 最小窗口子串的起始和结束位置

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]]; // 将窗口右侧的字符加入 cnt 中
            }
            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]]; // 将窗口左侧的字符从 cnt 中减去
                }
                ++l; // 缩小窗口
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len); // 返回最小窗口子串
    }
};