76. 最小覆盖子串。优化官方题解！

leetcode原题如下：

        给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

解题思路---滑动窗口

如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

官方题解：

    Map<Character, Integer> ori = new HashMap<Character, Integer>();Map<Character, Integer> cnt = new HashMap<Character, Integer>();public String minWindow(String s, String t) {Map<Character, Integer> ori = new HashMap<>();Map<Character, Integer> cnt = new HashMap<>();// 预处理，初始化 ori 表for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);ori.put(c, ori.getOrDefault(c, 0) + 1);}int l = 0, r = 0;int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;int sLen = s.length();int required = ori.size();  // 需要匹配的字符种类数量int formed = 0;  // 已经匹配的字符种类数量while (r < sLen) {char c = s.charAt(r);cnt.put(c, cnt.getOrDefault(c, 0) + 1);if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {formed++;}while (formed == required && l <= r) {if (r - l + 1 < len) {len = r - l + 1;ansL = l;ansR = l + len;}char leftChar = s.charAt(l);cnt.put(leftChar, cnt.get(leftChar) - 1);if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {formed--;}l++;}r++;}return ansL == -1 ? "" : s.substring(ansL, ansR);}

注意：这里 t 中可能出现重复的字符，所以我们要记录字符的个数。

考虑如何优化？ 如果 s=XX⋯XABCXXXX,t=ABC，那么显然 [XX⋯XABC]是第一个得到的「可行」区间，得到这个可行区间后，我们按照「收缩」窗口的原则更新左边界，得到最小区间。我们其实做了一些无用的操作，就是更新右边界的时候「延伸」进了很多无用的 X，更新左边界的时候「收缩」扔掉了这些无用的 X，做了这么多无用的操作，只是为了得到短短的 ABC。没错，其实在 s 中，有的字符我们是不关心的，我们只关心 t中出现的字符，我们可不可以先预处理 s，扔掉那些 t 中没有出现的字符，然后再做滑动窗口呢？也许你会说，这样可能出现 XXABXXC的情况，在统计长度的时候可以扔掉前两个 X，但是不扔掉中间的 X，怎样解决这个问题呢？优化后的时空复杂度又是多少？代码给出优化的版本.

public class MinimumWindowSubstring {public String minWindow(String s, String t) {// 用于记录 t 中各字符需要匹配的次数Map<Character, Integer> ori = new HashMap<>();// 用于记录当前窗口中各字符已匹配的次数Map<Character, Integer> cnt = new HashMap<>();// 预处理，初始化 ori 表for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);ori.put(c, ori.getOrDefault(c, 0) + 1);}int l = 0, r = 0; // 窗口的左右边界int len = Integer.MAX_VALUE; // 记录当前最小窗口的长度int ansL = -1, ansR = -1; // 记录当前最小窗口的左右边界int sLen = s.length(); // 字符串 s 的长度int required = ori.size(); // 需要匹配的字符种类数量int formed = 0; // 已经匹配的字符种类数量// 右指针滑动while (r < sLen) {char c = s.charAt(r);cnt.put(c, cnt.getOrDefault(c, 0) + 1);// 如果当前字符在 ori 表中，并且已匹配次数等于 ori 表中的次数，增加已匹配字符种类数量if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {formed++;}// 左指针滑动，窗口收缩while (formed == required && l <= r) {// 更新最小窗口的长度和边界if (r - l + 1 < len) {len = r - l + 1;ansL = l;ansR = l + len;}// 移动左指针，减少已匹配字符的次数char leftChar = s.charAt(l);cnt.put(leftChar, cnt.get(leftChar) - 1);// 如果左边界字符在 ori 表中，并且减少后的次数小于 ori 表中的次数，减少已匹配字符种类数量if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {formed--;}l++;}// 右指针继续滑动r++;}// 返回最小窗口对应的子串return ansL == -1 ? "" : s.substring(ansL, ansR);}
}

这段代码中的核心思想是使用滑动窗口来找到包含字符串 t 中所有字符的最小窗口。下面是代码中各部分的解释：

1. ori 和 cnt 的初始化：

   • ori 表用于记录字符串 t 中各字符需要匹配的次数。
   • cnt 表用于记录当前窗口中各字符已匹配的次数。

2. 预处理，初始化 ori 表：

   • 遍历字符串 t，将其中各字符及其需要匹配的次数记录在 ori 表中。

3. 窗口的左右边界 l 和 r：

   • 使用两个指针 l 和 r 来确定窗口。

4. required 和 formed：

   • required 记录需要匹配的字符种类数量，即 ori 表的大小。
   • formed 记录已经匹配的字符种类数量，初始为 0。

5. 右指针滑动（while (r < sLen)）：

   • 不断移动右指针 r，直到窗口包含了字符串 s 中的所有字符。

6. 左指针滑动，窗口收缩（while (formed == required && l <= r)）：

   • 移动左指针 l，尝试缩小窗口的大小。
   • 更新最小窗口的长度和边界。

7. 左右指针继续滑动，直至右指针到达字符串末尾：