76. 最小覆盖子串

题目链接

解题思路

• 求最小子串问题，第一时间，想「以i开头的结果是什么」，求出所有的结果，最优的便是；或者「以i结尾的结果是什么」，求出所有的结果，最优的便是
• 这个题使用「以i开头的结果是什么」，假设是[i, j]然后再求i+1的结果时，我们发现，只需要把i位置的字符去掉，就可以知道是否满足结果，如果不满足，我们可以直接把j往后接着找。有点像动态规划的思想，我知道了dp[i]，然后dp[i + 1]就可以利用dp[i]的结果，快速得到。
• 其实这个题是一个「滑动窗口」的问题。i开头，滑到j，也就是[i, j]就是i的结果，然后把i移除窗口，如果仍然满足结果，那i+1的结果就是[i + 1, j]，如果不满足，j再右移，就是滑动窗口的做法。
• 一些细节
  • 1️⃣怎么知道「j滑到哪里才满足」？可以用一个map，key就是某个字符，value就是该字符需要的次数。假设一个map，有map['a'] = 2，a字符需要2次。当遇到a之后，减减，当a减到0的时候，我们就能知道，a这个字符满足了，所以我们还需要用一个变量count记录，有几个字符已经满足了。假设map的大小是5，就说明，一共有5种字符，当count == 5时，就说明全部满足了。
  • 2️⃣得到i的结果[i, j]后，怎么把i移除？如果i在map里，现在i被移除了，所以map中对应的字符要++。
  • 那我怎么知道把i移除之后，i+1是否满足呢？还是count变量，当移除i，i对应的字符在map中，map就要++，如果++后，大于0了，说明，不满足了。所以，这里又有一个问题，1️⃣中，遇到map中的字符，就要减减，减到0后还要减吗？要减！因为i移除之后，map要加加，如果此时还是小于等于0，那就说明i+1还是满足条件的。
  • 总结一下：
    • 当遍历到的字符，是需要的，map中对应的字符就要减减，如果减减后，等于0了，那么count++，当count==5时，就说明满足条件了
    • 当移除i时，如果在map中，那么对应的字符就要加加，如果加加后，大于1了，那么count--，此时j就要往右滑了。

代码

class Solution {
public:
    string minWindow(string s, string t) {
        int ans_len = INT32_MAX;    // 答案的长度
        int ans_index = -1;         // 答案的开始下标
        unordered_map<char, int> need;     // 需要满足的字符
        int count = 0;
        // 构造需要满足的字符
        for (auto &it : t) {
            need[it]++;
        }
        int n = s.size();
        int j = -1;    // 窗口右边界
        for (int i = 0; i < n; ++i) {     // 以i开头的答案是什么？
            // 将i - 1移出窗口
            if (i - 1 >= 0 && need.count(s[i - 1]) != 0) {
                if (need[s[i - 1]]++ == 0) {   // 等同于need[s[i - 1]]++; if (need[s[i - 1]] > 0)
                    count--;
                }
            }
            while(j + 1 < n && count != need.size()) {    // 如果不满足条件  j要往右扩
                j++;
                if (need.count(s[j]) != 0) {
                    if (need[s[j]]-- == 1) {   // 等同于need[s[j]]--; if (need[s[j]] == 0)
                        count++;
                    }
                }
            }
            if (count == need.size()) {   // 满足要求
                if (j - i + 1 < ans_len) {   // 如果能更新
                    ans_len = j - i + 1;
                    ans_index = i;
                }
            } else {     // j都越界了  还没满足要求  说明满足不了了 后面的也满足不了了
                break;
            }
        }
        if (ans_index == -1) {   // 没有找到
            return "";
        }
        return s.substr(ans_index, ans_len);
    }
};