题目

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

滑动窗口

定义左右指针控制窗口内元素增减，也就是控制了窗口向右移动。首先，右指针向右移动知道窗口内的字符串包含了t中的所有字符。然后控制左指针向右移动缩小窗口，直到窗口内元素不包含t中所有字符，在移动左指针更新最小长度。判断窗口内元素是否包含t中所有字符可以使用一个变量valid如果窗口内右指针指向元素的个数小于t中该元素的个数则valid++,如果窗口内的字符串包含了t中所有元素则valid == t.length, 这时候可以移动左指针，当左指针指向的元素个数等于t中该元素的个数时valid--，此时窗口内的元素不在覆盖t中所有字符，从而继续移动右指针。

class Solution {
    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 || tLen == 0 || sLen < tLen) return "";

        int[] need = new int[128];
        int[] window = new int[128];

        char[] sArr = s.toCharArray();

        for (char c : t.toCharArray()) {
            need[c]++;
        }

        int left = 0, right = 0, start = 0;
        int len = Integer.MAX_VALUE;
        int valid = 0;
        while (right < sLen ) {
            char c = sArr[right];
            if (need[c] == 0) {
                right++;
                continue;
            }
            if (window[c] < need[c]) {
                    valid++;
            }
            window[c]++;
            right++;
        
            while (valid == tLen) {
                if (right - left < len) {
                    len = right - left; 
                    start = left;
                }
                char d = sArr[left];
                if (need[d] == 0) {
                    left++;
                    continue;
                }
            
                if (window[d] == need[d]) {
                    valid--;
                }
                window[d]--;
                left++;
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}