🚩传送门：牛客题目
力扣题目

题目

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

注意：

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

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC”

解题思路：双指针滑动窗口

本问题要求我们返回字符串 [NC]28. 最小覆盖子串 - 图1 中包含字符串 [NC]28. 最小覆盖子串 - 图2 的全部字符的最小窗口。我们称包含 [NC]28. 最小覆盖子串 - 图3 的全部字母的窗口为「可行」窗口。

我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 [NC]28. 最小覆盖子串 - 图4 指针，和一个用于「收缩」窗口的 [NC]28. 最小覆盖子串 - 图5 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 [NC]28. 最小覆盖子串 - 图6 上滑动窗口，通过移动 [NC]28. 最小覆盖子串 - 图7 指针不断扩张窗口。当窗口包含 [NC]28. 最小覆盖子串 - 图8 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。
[NC]28. 最小覆盖子串 - 图9
注意：这里 **t** 中可能出现重复的字符，所以我们要记录字符的个数。

考虑如何优化？
如果 [NC]28. 最小覆盖子串 - 图10，[NC]28. 最小覆盖子串 - 图11，那么显然 [NC]28. 最小覆盖子串 - 图12 是第一个得到的「可行」区间，得到这个可行区间后，我们按照「收缩」窗口的原则更新左边界，得到最小区间。我们其实做了一些无用的操作，就是更新右边界的时候「延伸」进了很多无用的 [NC]28. 最小覆盖子串 - 图13，更新左边界的时候「收缩」扔掉了这些无用的 [NC]28. 最小覆盖子串 - 图14，做了这么多无用的操作，只是为了得到短短的 [NC]28. 最小覆盖子串 - 图15。因此我们需要在最开始的时候对于临时表为空，且不在字串中的字符进行丢弃，将 [NC]28. 最小覆盖子串 - 图16 这情况的无用的 [NC]28. 最小覆盖子串 - 图17全部丢弃。

复杂度分析

时间复杂度： [NC]28. 最小覆盖子串 - 图18 

  1.   - 开始需要对 ![](https://cdn.nlark.com/yuque/__latex/cead1760d9d5723460c4b8d4028f113a.svg#card=math&code=t&id=iAq4B) 中的元素都执行一次插入，最坏情况下左右指针对 ![](https://cdn.nlark.com/yuque/__latex/79ce3c7a71877c2ff01695e38ade43ca.svg#card=math&code=s&id=stWmU) 的每个元素各遍历一遍，每次检查是否可行会遍历整个 ![](https://cdn.nlark.com/yuque/__latex/cead1760d9d5723460c4b8d4028f113a.svg#card=math&code=t&id=OW2Jo) 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 ![](https://cdn.nlark.com/yuque/__latex/a42a4fc28b384cc408de066beed57485.svg#card=math&code=C&id=DGGfu) ，则渐进时间复杂度为  ![](https://cdn.nlark.com/yuque/__latex/cce756f459876c84d2f26ff4a75f317b.svg#card=math&code=%5Csmall%20O%28C%E2%8B%85%E2%88%A3s%E2%88%A3%2B%E2%88%A3t%E2%88%A3%29&id=KfVB4) 。

空间复杂度：[NC]28. 最小覆盖子串 - 图19 

  1.   - 这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 ![](https://cdn.nlark.com/yuque/__latex/a42a4fc28b384cc408de066beed57485.svg#card=math&code=C&id=bueHL) ，则渐进空间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/12f94e418c4fdaad4ea0009aa2a83a68.svg#card=math&code=%5Csmall%20O%28C%29&height=20&id=b9ASP) 。

我的代码

  1. public class Solution {
  3.     public boolean CharEnoughInT( HashMap<Character,Integer>submap, HashMap<Character,Integer>tempmap){
  4.         // 字符都不满足
  5.         if(submap.size()>tempmap.size()) return false;
  6.         // entry 是子串必须要具备的
  7.         for(Map.Entry<Character,Integer> entry:submap.entrySet()){
  8.             // 字串当前字符个数多于临时串说明不匹配
  9.             if(entry.getValue()>tempmap.getOrDefault(entry.getKey(),0))
  10.                 return false;
  11.         }
  12.         return true;
  13.     }
  15.     public String minWindow (String S, String T) {
  16.         // write code here
  17.         HashMap<Character,Integer>submap=new HashMap<>();    // 记录T的哈希表
  18.         HashMap<Character,Integer>tempmap=new HashMap<>();    // 记录临时串的哈希表
  19.         // 将字串的哈希打表
  20.         for(int i=0;i<T.length();i++){
  21.             char c=T.charAt(i);    // 得到T的当前字符
  22.             submap.put(c,submap.getOrDefault(c,0)+1);
  23.         }
  24.         // 双指针
  25.         int l=0,r=0;
  26.         int resL=0,resR=Integer.MAX_VALUE;
  27.         // 遍历右指针
  28.         for(r = 0;r<S.length();r++){
  29.             char c=S.charAt(r);    // 得到S的当前字符
  30.             // 如果临时字符是空的,当前字符还不在字串中那么可以lr直接跳过
  31.             if(tempmap.size()==0 && !submap.containsKey(c)){
  32.                 l=r+1;
  33.                 continue;
  34.             }
  35.             // 插入当前字符串,由于不清楚是否存在先查,查到原基础+1,查不到设置1
  36.             tempmap.put(c,tempmap.getOrDefault(c,0)+1);
  37.             // 此时临时字符串不是空的,判断是否满足条件临时串覆盖了字串
  38.             while(CharEnoughInT(submap,tempmap)){
  39.                 // 满足字串,查看能否刷新长度
  40.                 if((resR-resL)>(r-l)){
  41.                     resL=l;
  42.                     resR=r;
  43.                 }
  44.                 // l指针移动,并移除当前l的字符
  45.                 char Slc=S.charAt(l);               // 获取l指针在S串中的字符
  46.                 int SlcTempnum=tempmap.get(Slc);    // 得到临时map中该字符的数量
  47.                 tempmap.put(Slc,SlcTempnum-1);      // 将当前字符数-1
  48.                 if(SlcTempnum==0) tempmap.remove(Slc); // 如果当前字符数为0,移除出map
  49.                 l++;
  50.             }
  51.         }
  52.         if(resR==Integer.MAX_VALUE) return "";
  53.         return S.substring(resL,resR+1);
  54.     }
  55. }