BM90 题解 | #最小覆盖子串#

心路历程：

刚开始有思考过，用快慢指针卡出一个窗口，就是这个窗口是固定的，所以后续，就卡壳了，现在发现了，还可以用动态缩放的窗口，就豁然开朗了。

滑动窗口的基本思想：

1. 用两个字典分别维护窗口中字符的统计数量、以及被求解子串中字符的统计数量，本题的hash
2. 用双指针遍历主字符串，双指针的初始值均为0，窗口的范围是[slow, fast)（左闭右开）
3. 遍历过程中，不断增大、缩小窗口，并更新状态，cnt、left、right、hash。

动态窗口的主要实现模版如下：

int[] hash = new int[128];

int fast =0, slow = 0; //移动的快慢指针

int left =-1, right = -1 //记录符合添加的窗口坐标

for(; fast<S.length(); fast++) {

hash[S.chatAt(i)] ++;

while(条件判断) { //用while可以执行多次符合条件的slow++，if不行

if(cnt> fast-slow+1) {

cnt = fast - slow +1;

left = slow；

right = fast;

}

hash[T.chatAt(slow)] --;

slow++；

}

}

解题思路：

如上文所描述，不用去死记硬背各种代码，而是，记住那个图，根据实际的图，不断的去用数据结构和循环逻辑，实现整个功能。

import java.util.*;


public class Solution {
    /**
     * 本题使用的是窗口滑动思想
     * 窗口滑动是动态变化的，不是固定的，
     * 先fast++找符合添加的 后slow++缩小窗口
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {

        if(S==null|| S.length()==0 || T==null || T.length()==0) {
            return "";
        }
        
        int cnt = S.length()+1; //统计最小窗口大小
        int[] hash = new int[128];//统计目标字符出现次数
        int fast = 0, slow = 0; //记录快慢窗口
        int left = -1, right = -1; //记录满足条件的最小窗口位置
        
        for(int i=0; i<T.length(); i++) {
            hash[T.charAt(i)] -= 1;
        }

        for(fast = 0; fast<S.length(); fast++) {
            char c = S.charAt(fast);
            hash[c] += 1;
            while(check(hash)) {
                if(cnt>fast - slow +1) {
                    cnt = fast-slow +1;
                    left = slow;
                    right = fast;
                }
                hash[S.charAt(slow)] -= 1;
                slow++;
            }
        }

        if(left==-1) {
            return "";
        }
        return S.substring(left, right+1);
    }

    boolean check(int[] hash) {
        for(int i=0; i<hash.length; i++) {
            if(hash[i]<0) {
                return false;
            }
        }
        return true;
    }

}