1、前言

题目描述

2、思路

采用滑动窗口的思路，首先滑动窗口的 right 一直往右边扩展，直到包含 t 中所有的字符。然后滑动窗口的 left 往右收缩，边收缩边更新最小 len，知道 right 已经到达了 s 的长度停止。

滑动窗口很符合人类的直觉理解，但是不同的题目滑动窗口应该怎么定义呢？一般来说，s1 是否包含 s2 之类的题，说明滑动窗口最初的长度就为 s2 长度，然后不断的在 s1 上滑动。而对于那种某个字符串 s 最长的无重复子串之类的，因为窗口定义是不定的，所以需要定义两个指针，初始 right 往右移，出现重复的 left 往右移，直到 window 里没有重复的字符。

3、代码

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();

        int m = s.length(), n = t.length();
        if(m < n){
            return "";
        }
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0, length = Integer.MAX_VALUE, valid = 0, start = 0;
        while(right < m){
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            right++;

            if(need.containsKey(c) && window.get(c).equals(need.get(c))){
                valid++;
            }

            while(valid == need.size()){
                if(right - left < length){
                    length = right - left;
                    start = left;
                }

                char c1 = s.charAt(left);
                left++;
                if(need.containsKey(c1) && window.get(c1).equals(need.get(c1))){
                    valid--;
                }
                window.put(c1, window.get(c1) - 1);
                if(window.get(c1) == 0){
                    window.remove(c1);
                }
            }
        }

        return length == Integer.MAX_VALUE ? "" : s.substring(start, start + length);
    }
}