题目: 最小覆盖子串

分析

这是一种优化的暴力方法，首先创建两个指针，一个指向字符串的开始，另一个指向字符串的结尾，然后不断将右指针向右移动，直到找到包含T中所有字符的子串。然后将左指针向右移动，以找到最短的包含T中所有字符的子串。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
public:
    string minWindow(string s, string t) {
        int left = 0, right = 0, count = 0, minLen = INT_MAX, start = 0;
        unordered_map<char, int> mp;
        for (auto c : t) {
            mp[c]++;
        }
        count = mp.size();
        while (right < s.size()) {
            if (mp.find(s[right]) != mp.end()) {
                mp[s[right]]--;
                if (mp[s[right]] == 0) {
                    count--;
                }
            }
            right++;
            while (count == 0) {
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }
                if (mp.find(s[left]) != mp.end()) {
                    mp[s[left]]++;
                    if (mp[s[left]] > 0) {
                        count++;
                    }
                }
                left++;
            }
        }
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

方法二：哈希表 + 双指针

首先遍历T中的所有字符并将其添加到哈希表中，然后使用两个指针left和right分别指向S的开头和结尾。移动right指针，每次将右边的字符添加到哈希表中，并检查是否在T中出现。如果存在，递减哈希表中相应字符的计数器。当哈希表中所有字符的计数器都小于等于零时，表示当前窗口包含T中的所有字符，记录子串长度并将left指针向右移动以找到更短的子串。

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> mp;
        for (char c : t) {
            mp[c]++;
        }
        int left = 0, right = 0, count = t.size(), minLen = INT_MAX, start = 0;
        while (right < s.size()) {
            if (mp[s[right]]-- > 0) {
                count--;
            }
            right++;
            while (count == 0) {
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }
                if (mp[s[left]]++ == 0) {
                    count++;
                }
                left++;
            }
        }
    }
}