题目

the leetcode link

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

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

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
示例 2：
输入：s = “a”, t = “a”
输出：”a”
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

特点

1. 为了使用队列，减少对哈希表数组操作的遍历次数，设置了zoreNeed平衡点，定义了匹配字符在窗口中是否需要的平衡界限
2. 左指针采用队列记录，实现左指针跳跃，相比左指针+1循环的方式减少了遍历次数

   代码

   class Solution {
       public String minWindow(String s, String t) {
           if (s == "" || t == "" || s.length() < t.length()) {
               return "";
           }
   
           char[] ss = s.toCharArray();
           char[] tt = t.toCharArray();
           int zoreNeed = ss.length; //设置0平衡，定义了匹配字符在窗口中是否需要的平衡界限，作用是：使匹配字符的need最小无法达到0， 非匹配字符都是need=0，保证能区分开，来决定能否加入队列
   
           //1. 创建hash表：匹配字符-> zoreNeed + 实际需要数；非匹配字符 -> 0
           int[] need = new int[123];
           for(char c: tt){
               if(need[c]==0) need[c]+=zoreNeed;
               need[c]++;
           }
   
           Queue<Integer> queue = new LinkedList<>(); //2. 匹配字符位置队列
   
           int needSum = tt.length,  ansStart=0,  ansSize=Integer.MAX_VALUE;
           //3. 窗口随着右指针end递增而增大
           for(int start = 0, end= 0; end<ss.length; end++){
   
               if(need[ss[end]]>zoreNeed){ //4. 判断窗口是否需要当前字符,需要的话needSum-1
                   needSum--;
               }
   
   
               if(need[ss[end]]>0){ //5. 若是则匹配字符加入队列
                   queue.add(end);
                   need[ss[end]]--;
               }
   
                //6. 窗口匹配成功
               if(needSum == 0){
                   //6.1 从队列中不断取start，窗口随着左指针start递增而增大
                   start = queue.poll();  //此时队列不可能为空，取队列第一个匹配字符（左指针指向第一次匹配字符位置 或 上一次成功匹配后将左指针指向下一个匹配字符位置）
                   while(need[ss[start]]<zoreNeed){ //缩小窗口，直到刚好匹配则结束
                       need[ss[start]]++;
                       start = queue.poll();  //取出并删掉多余的匹配字符
                   }
   
                   //6.2 取最小窗口
                   if(end-start<ansSize){
                       ansStart = start;
                       ansSize = end-start;
                   }
   
                   //6.3 左指针右移，继续缩小窗口。 这里只先释放增加左指针指向匹配字符的需要数，真正右移是在等下一次匹配成功后，第一次调用 start = queue.poll();
                   need[ss[start]]++;
                   needSum++;
               }
   
           }
           return ansSize == Integer.MAX_VALUE? "" :s.substring(ansStart, ansStart+ansSize+1);
       }
   }