76. 最小覆盖子串

题目链接：力扣

解题思路：滑动窗口

1. 因为只需要最小子串中包含t中的所有字符即可，顺序不重要，所以可以先统计一下 t 中每个字符出现的次数，使用map进行统计：
   1. key表示t中的字符，
   2. value表示字符的个数：值为正数时表示滑动窗口中需要value个字符，值为负数时表示滑动窗口中多余了 -value个字符
2. 初始值：
   1. result = ""：保存最小子串
   2. num = 0：窗口中包含的 t 中的有效字符个数（如果t中字符a有两个，滑动窗口中已经有两个a了，这个时候右遇到一个a，num并不加1，因为这个a是无效的）
   3. left = 0：滑动窗口的左边界
   4. right = 0：滑动窗口的右边界
3. 不断左移滑动窗口的右边界，当num==t.length，找到了一个字串包含所有t中的字符，但是这个时候，滑动窗口的左边界可能会有一些无效的字符或者多余的字符：
   1. 比如 BABC子串，包含t = BC，但是前面的BA是无效的，可以删去，最小子串为BC
4. 具体移动过程如下，如果right < s.length，则一直往右移动：
   1. 如果 map.containsKey(s.charAt(right))：当前字符是 t 中的字符
      1. 如果map.get(s.charAt(right)) > 0：说明滑动窗口中包含当前字符的个数小于t中的字符个数，令 num++
      2. map.put(s.charAt(right)，map.get(s.charAt(right))-1)：令当前字符个数 -1，方便后面缩小滑动窗口的左边界
   2. 如果 num == t.length：说明滑动窗口中已经包含了所有t中的字符，但这个时候左边界可能有一些不在t中的字符或者多余的字符。需要循环缩小左边界：
      1. 如果 左边界的字符不在 t中，或者 map.get(s.charAt(left)) < 0，即字符有多余，这两种情况下都需要收缩：
         1. 如果在t中，并且map中的值小于0，说明左边界这个字符是多余的，令map中的值+1
         2. left++
   3. 如果result.equal("")或者 right - left +1 < result.length()：更短的子串
      1. 令result = s.substring(left,right+1)

AC代码：
 

class Solution {public static String minWindow(String s, String t) {char[] sStr = s.toCharArray();char[] tStr = t.toCharArray();Map<Character, Integer> map = new HashMap<>();for (char c : tStr) {map.put(c, map.getOrDefault(c, 0) + 1);}int left = 0;String result = "";//记录滑动窗口中包含多少个t中的字符int num = 0;for (int right = 0; right < sStr.length; right++) {if (map.containsKey(sStr[right])) {if (map.get(sStr[right]) > 0) {num++;}map.put(sStr[right], map.get(sStr[right]) - 1);}if (num == tStr.length) {//缩小窗口右边界while (!map.containsKey(sStr[left]) || map.get(sStr[left]) < 0) {if (map.containsKey(sStr[left])) {map.put(sStr[left], map.get(sStr[left]) + 1);}left++;}if (result.equals("") || right - left + 1 < result.length()) {result = s.substring(left, right + 1);}}}return result;}
}

使用集合进行统计滑动窗口中需要的字符个数或者多余的字符个数，效率较低，可以使用hash表进行优化，思路类似，只不过将map换成hash表：

AC代码

class Solution {public static String minWindow(String s, String t) {char[] sStr = s.toCharArray();char[] tStr = t.toCharArray();int[] hash = new int[128];for (char c : tStr) {hash[c]++;}int left = 0;String result = "";//记录滑动窗口中包含多少个t中的字符int num = 0;for (int right = 0; right < sStr.length; right++) {hash[sStr[right]]--;if (hash[sStr[right]] >= 0) {num++;}while (num == tStr.length && hash[sStr[left]] < 0) {hash[sStr[left++]]++;}if (num == tStr.length && (result.equals("") || right - left + 1 < result.length())) {result = s.substring(left, right + 1);}}return result;}
}