题解 | #最小覆盖子串，双指针，滑动窗口#

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        if(S.length() == 0 || T.length() == 0) return "" ;
        int minCount = Integer.MAX_VALUE ;
        int[] hash = new int[128] ;
        for(int i = 0 ; i < T.length() ; i ++) {
            hash[T.charAt(i)] -- ;
        }
        int minLen = Integer.MAX_VALUE ;//记录最小覆盖子串的长度
        int ri = 0 ;//记录最小覆盖子串的左边界
        int rj = 0 ;//记录最小覆盖子串的右边界
        int f = 0 ;//窗口右边界
        int s = 0 ;//窗口左边界
        while(f < S.length()) {//右边界向右移动
            hash[S.charAt(f)]++ ;//将当前右边界坐对对应的字符加入hash
            while(s <= f && check(hash)) {//如果已经覆盖了,则不断让左边界右移，寻找最短的满足要求的子串
                if(f - s + 1 < minLen) {//更新小覆盖子串的记录
                    minLen = f - s + 1 ;
                    ri = s ;
                    rj = f ;
                }
                hash[S.charAt(s)] -- ;//将左边界移除hash
                s ++ ;//左边界右移
            }
            f ++ ;//右边界右移
        }
        if(f - s + 1 > S.length()) {//如果右边界超出S时左边界都没动过，说明不存在覆盖子串
            return "" ;
        } else {//截取
            return S.substring(ri , rj + 1) ;
        }
    }
    public boolean check(int hash[]) {
        for(int i = 0 ; i < hash.length ; i ++) {
            if(hash[i] < 0) {
                return false ;
            }
        }
        return true ;
    }
}