链接：https://www.nowcoder.com/questionTerminal/c466d480d20c4c7c9d322d12ca7955ac?f=discussion来源：牛客网[编程题]最小覆盖子串热度指数：76918时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M算法知识视频讲解给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。数据范围：0≤∣S∣,∣T∣≤100000≤∣S∣,∣T∣≤10000，保证s和t字符串中仅包含大小写英文字母要求：进阶：空间复杂度 O(n)O(n) ， 时间复杂度 O(n)O(n)例如：S="XDOYEZODEYXNZ"T="XYZ"找出的最短子串为"YXNZ".注意：如果 s 中没有包含 t 中所有字符的子串，返回空字符串 “”；满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。示例1输入"XDOYEZODEYXNZ","XYZ"输出"YXNZ"示例2输入"abcAbA","AA"输出"AbA"import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param S string字符串* @param T string字符串* @return string字符串*/public String minWindow (String S, String T) {HashMap<Character, Integer> hs = new HashMap<>();HashMap<Character, Integer> ht = new HashMap<>();String shortString = "";for (char c : T.toCharArray()) {ht.put(c, ht.getOrDefault(c, 0) + 1);}int count = 0;int len = 99999;for (int i = 0, j = 0; i < S.length(); i++) { // j head pos, i bottom poshs.put(S.charAt(i), hs.getOrDefault(S.charAt(i), 0) + 1);if (ht.containsKey(S.charAt(i)) &&ht.get(S.charAt(i)) >= hs.get(S.charAt(i))) { // 找到ht中包含的字符， 且数量小于ht该字符的总数，代表需要计数count ++;}// 缩头。当头指针小于尾指针 且 ht中不含字符或小于该位置的字符的数量while (i > j && (!ht.containsKey(S.charAt(j)) ||ht.get(S.charAt(j)) < hs.get(S.charAt(j)))) {hs.put(S.charAt(j), hs.getOrDefault(S.charAt(j), 0) - 1);j++;}if (count == T.length() && i - j + 1 < len) {len = i - j + 1;shortString = S.substring(j, i + 1);}}return shortString;}}