题解 | #最小覆盖子串#

public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        /*
        1) left开始指向0， right一直后移，直到right - left区间包含T中所有字符。
        记录窗口长度minLen
        2) 然后left开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
        包含在窗口，
        3) 继续后移right，直到T中的所有字符被包含在窗口，重新记录最小的窗口minLen。
        4) 如此循环直到right到S中的最后一个字符。
        时间复杂度为O(n)
         */
        // write code here
        //由于S和T中均只包含大小写字母，所以可以用一个大小为128的数组存储其字符出现次数，数组下标对应字符值
        int[] map = new int[128];//A-Z==65-91  a-z==97-123
        for (int i = 0; i < T.length(); i++) {
            map[T.charAt(i)]++;
        }
        //start记录当前最小滑动窗口的开始位置。left和right为当前滑动窗口的左右指针，
        // 当满足left和right对应的滑动窗口包含T的所有字符，且该滑动窗口的大小小于minLen时，更新当前滑动窗口大小，及其开始位置
        int start = 0, left = 0, right = 0,count = T.length(),minLen = Integer.MAX_VALUE;
        while (right<S.length()){
            if(map[S.charAt(right)] >0){//先判断，再减去1，若该值不存在，则会被更新为-1，若该值存在被更新为0
                count--;
                map[S.charAt(right)]--;
                right++;
            }else{
                map[S.charAt(right)]--;
                right++;
            }

            while (count == 0){
                if(right-left < minLen){
                    start = left;
                    minLen = right-left;
                }

                if(map[S.charAt(left)] == 0){
                    count++;
                    map[S.charAt(left)]++;
                    left++;
                }else {
                    map[S.charAt(left)]++;
                    left++;
                }
            }
        }

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

}