更新：文明

题目

https://leetcode-cn.com/problems/minimum-window-substring/

分析

使用滑动窗口，开始时 i，j 指向第一个。
1.j一直+1，直到包含所有需要的元素。
2.i一直+1，直到遇到了一个必须包含的元素。记录下此时的 j-i+1 字串长度，并保存最小值。
3.再让 i+1，此时不满足条件了，回到第1步，让 j 后移。循环这些步骤直到 j 越界。
如何判断滑动窗口包含了T的所有元素？
用数组 need 保存各字符需要的个数。一开始滑动窗口为空，用T中各元素来初始化这个need。
当滑动窗口扩展或者收缩的时候，去维护这个need。当滑动窗口包含某个元素，need中这个元素的数量减1，代表所需元素减少了1个；当滑动窗口移除某个元素，need中这个元素的数量加1。
如果每次判断滑动窗口是否包含了所有元素，都去遍历一遍need会耗时，所以使用一个count来表示所需元素数量，如果count为0则说明滑动窗口已包含所有元素。

复杂度

时间复杂度：O(n)。
空间复杂度：O(1)。使用了固定长度为128的need数组。

代码

class Solution {
    public String minWindow(String s, String t) {
        if(t.length()>s.length())
            return "";
        //初始化need数组
        int[] need=new int[128];
        for(int i=0;i<t.length();i++){
            need[t.charAt(i)]++;
        }
        //初始化左右指针
        int left=0,right=0;
        //需要的字符数
        int count=t.length();
        //最小字串开始位置
        int start=0;
        //最小字串长度
        int min=Integer.MAX_VALUE;  
        while(right<s.length()){
            //需要当前right字符
            if(need[s.charAt(right)]>0){
                //总需要字符数-1
                count--;
            }
            //把right字符加入窗口
            need[s.charAt(right)]--;

            //滑动窗口已包含所有所需字符
            if(count==0){
                while(left<right&&need[s.charAt(left)]<0){
                    //释放右边移动出窗口的字符
                    need[s.charAt(left)]++;
                    left++;
                }
                //跳出上面的循环，此时left所在位置的字符是被需要的
                if(right-left+1<min){
                    min=right-left+1;
                    start=left;
                }
                //释放这一个left的字符
                //并且重新进入大的循环，即right右移
                need[s.charAt(left)]++;
                left++;
                count++;
            }
            //right右移一位
            right++;
        }
        return min==Integer.MAX_VALUE?"":s.substring(start,start+min);
    }
}

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> need=new HashMap<>();
        int needSum=t.length();//共需要的字符数
        for(char c:t.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);//这个字符的需要数+1
        }
        int left=0,right=0;
        int start=0;//最小子串开始位置
        int minLen=Integer.MAX_VALUE;
        while(right<s.length()){
            if(need.getOrDefault(s.charAt(right),0)>0){//需要
                needSum--;
            }
            need.put(s.charAt(right),need.getOrDefault(s.charAt(right),0)-1);
            if(needSum==0){//已满
                //去除头部不需要的left
                while(left<right&&need.get(s.charAt(left))<0){
                    need.put(s.charAt(left),need.getOrDefault(s.charAt(left),0)+1);
                    left++;
                }
                //此时left是需要的
                //更新最大值和起点
                if(right-left+1<=minLen){
                    minLen=Math.min(minLen,right-left+1);
                    start=left;
                }
                //去掉left，使子串不满足条件
                need.put(s.charAt(left),need.getOrDefault(s.charAt(left),0)+1);
                needSum++;
                left++;
            }
            right++;
        }
        return minLen==Integer.MAX_VALUE?"":s.substring(start,start+minLen);
    }
}

结果