滑动窗口算法 / 双指针算法

定义两个哈希表，一个 hs 用于存储窗口 [i, j] 中字符出现的次数，一个 ht 用于存储字符串 t 中每个字符出现的次数。

定义一个变量 cnt 用于记录窗口中包含字符串 t 的有效字符个数（多的不算）。

先将 t 中每个字符和出现次数存入哈希表，然后遍历字符串 s

滑动窗口的常规步骤：

  1. 将当前字符 s[i] 加入到窗口中，hs[s[i]] ++

  2. 判断当前字符是否为有效字符 hs[s[i]] <= ht[s[i]] ，如果是则 cnt + 1

  3. 尝试更新指针 j，如果当前字符 s[j] 是多余字符（窗口内的 s[j] 字符出现次数已经大于字符串 t 中的这个字符）hs[s[j]] > ht[s[j]]，则将当前字符出现次数 - 1 同时指针后移

  4. 更新答案。如果答案为空或者比之前的长度更小，则更新

class Solution {
public:
    string minWindow(string s, string t) {
        // hs 是用于来记录窗口 [i, j] 中每个字符出现的次数，ht 是用来记录字符串 t 中每个字符出现的次数
        unordered_map<char, int> hs, ht;
        for (auto c : t) ht[c] ++ ;

        string res;
        // 表示窗口 [i, j] 中有效的字符个数（有效：如果加上当前字符 s[i]，能让 cnt 加 1 就是有效字符，否则就是无效字符）
        int cnt = 0;
        for (int i = 0, j = 0; i < s.size(); i ++ ) {
            // 把 s[i] 加到滑动窗口中
            hs[s[i]] ++ ;
            // 如果当前字符是有效字符，那么窗口内有效字符个数 + 1
            if (hs[s[i]] <= ht[s[i]]) cnt ++ ;
            // 尝试移动 j
            while (hs[s[j]] > ht[s[j]]) hs[s[j ++ ]] -- ;
            // 如果当前有效窗口个数等于 t 中的字符个数，更新答案
            if (cnt == t.size()) {
                if (res.empty() || i - j + 1 < res.size())
                    res = s.substr(j, i - j + 1);
            }
        }
        return res;
    }
};