题解 | #最小覆盖子串#

public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        
        int n = S.length();
        int m = T.length();
        //子串起点
        int start = 0;
        //子串长度 题目中长度小于10000
        int len = 10001;
        //统计T中字符出现的次数
        int[] map = new int[128];
        for(int i = 0;i< m;i++){
            map[T.charAt(i)] ++;
        }
        //滑动窗口边界 l r  ，count 字符串数量
        int l = 0, r = 0, count = m;
        while( r < n){
            //如果出现次数大于0  向左找到能匹配的最大右边界
            if(map[S.charAt( r ++)] -- > 0){
                count --;
            }
            //当前子串合法
            while(count == 0){
                if(len > r - l){
                    len = r- l;
                    start = l;
                }
                //这里就是滑动窗口了，如果符合规则下，第一个数在map里肯定是 0 ，窗口 l边界右移 消除的数量肯定要加 +
                if(map[S.charAt(l++)] ++ == 0){
                    count ++;
                }
            }
           
        }
        System.out.println(start);
        System.out.println(len);
         return len == 10001 ? "" :S.substring(start,start +len);
    }
}