class Solution {
public: 
    string minWindow(string S, string T) {
    vector<int> chars(128, 0);  // 表示目前每个字符串缺少的数量
    vector<bool> flag(128, false);  // 表示每个字符是否在T中存在
    // 先统计T中的字符情况
    for (int i = 0; i < T.size(); ++i)
    {
        flag[T[i]] = true;
        ++chars[T[i]];
    }

    // 移动滑动窗口，不断更改统计数据
    int cnt = 0, l = 0, min_l = 0, min_size = INT_MAX;
    for (int r = 0; r < S.size(); ++r)  // r为窗口右边界，l为窗口左边界
    {
        if (flag[S[r]]) {  // 如果遍历到T中的字符
            if (--chars[S[r]] >= 0)  // 减少结果中缺少的数量
                ++cnt;  // 统计结果中的字符
        }
        // 若目前滑动窗口已包含T中全部字符
        // 则尝试将l（左边界）右移，在不影响结果的情况下获得最短子字符串
        while (cnt == T.size())
        {
            if (r - l + 1 < min_size) {
                min_l = l;  // 更新最短字串的左边界
                min_size = r - l + 1; // 更新最短子串的大小
            }
            if (flag[S[l]] &&  // 若缩减的字符含有t中的字符
             ++chars[S[l]] > 0)  // 增加该字符在结果中缺少的数量
                --cnt;
            ++l;
        }
    }
    return min_size > S.size()? "": S.substr(min_l, min_size);  // 提取s中的子串
    }
};

复杂度分析

• 时间复杂度：最坏情况下左右指针对 s 的每个元素各遍历一遍，哈希表中对 s 中的每个元素各插入、删除一次，对 t 中的元素各插入一次。每次检查是否可行会遍历整个 tt 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 C，则渐进时间复杂度为O(C?∣s∣+∣t∣)
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。。
• 空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 C ，则渐进空间复杂度为 O?。