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