思路

• 双指针(滑动窗口)
• 预先将模式串加入到map中 统计每个字符
• 进窗口出窗口过程
• 进窗口:
  • 右指针入窗口
  • 当右指针指向的字符在need中时将其加入window
• 出窗口：当cnt == m 即匹配模式串时出窗口
  • 出窗口操作:记录当前子串长度，更新长度和起始点

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length();
        int m = t.length();
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        //先将模式串放入到need中
        for(int i = 0 ; i < m ; i++){
            char c = t.charAt(i);
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int len = Integer.MAX_VALUE,cnt = 0,start = 0;
        for(int i = 0 , j = 0 ; i < n ;i++){
            //左指针j右指针i
            char input = s.charAt(i);
            if(need.containsKey(input)){
                window.put(input,window.getOrDefault(input,0)+1);
                if(window.get(input).equals(need.get(input)))
                    cnt++;
            }

            while(cnt == need.size()){
                if(i - j + 1 < len){
                    len = i - j + 1;
                    start = j;
                }
                char out = s.charAt(j);
                j++;
                if(window.containsKey(out)){
                    if(window.get(out).equals(need.get(out)))
                        cnt--;
                    window.put(out,window.get(out)-1);
                }  
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
    }
}