题目描述

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”

说明

如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

题解

滑动窗口

本问题要求我们返回字符串 s 中包含字符串 tt 的全部字符的最小窗口。我们称包含 tt的全部字母的窗口为「可行」窗口。
我们可以用滑动窗口的思想解决这个问题，在滑动窗口类型的问题中都会有两个指针。一个用于「延伸」现有窗口的 r指针，和一个用于「收缩」窗口的 l指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

左右边界是交替滑动的,即同一时间只有一个边界在移动,要么在扩大子区间,要么在缩小覆盖范围.

public class lc76 {
    // 用于存放字符串T中各字符的频数
    int[] original = new int[128];
    // 用于存放当前窗口中各字符的频数
    int[] slide = new int[128];

    public String minWindow(String s, String t) {
        // T和S字符串的长度
        int tLen = t.length();
        int sLen = s.length();
        if (tLen > sLen) return "";
        // 将两个字符串转换成字符组
        char[] tChars = t.toCharArray();
        char[] sChars = s.toCharArray();

        // 将T字符串中各字符频数计算出来
        for (char c : tChars) {
            original[c]++;
        }

        // 初始化滑动窗口的边界
        int left = 0;
        int right = -1;
        // 当前滑动窗口的长度
        int len = 0;
        // 当前记录的最小覆盖子串长度
        int minLen = Integer.MAX_VALUE;
        // 当前记录的最小覆盖子串左边界
        int ansLeft = 0;
        // 当前记录的最小覆盖子串右边界
        int ansRight = 0;

        // 使用两个while循环实现左右指针的交替移动
        while (right < sLen) {
            // 移动右指针
            right++;
            // 若当前的字符存在于T字符串中,滑动窗口中该字符的频次加一
            if (right < sLen && original[sChars[right]] > 0) {
                slide[sChars[right]]++;
            }

            // 右指针每向右移动一位,就检查一下当前滑动窗口中是否覆盖全部的要求的字符
            // 若全覆盖,则循环移动左边界,直到无法满足全覆盖的条件;
            // 若没有全覆盖,则继续移动右边界,直到满足全覆盖.
            while (check(tChars) && left < sLen) {
                len = right - left + 1;
                if (len < minLen) {
                    minLen = len;
                    ansLeft = left;
                    ansRight = right;
                }

                // 每次移动左边界,都会减少一个字符.如果减少的字符恰好是需要覆盖的字符,则相应的频数减一
                if (original[sChars[left]] > 0) {
                    slide[sChars[left]]--;
                }
                // 左指针移动
                left++;
            }
        }
        // 若初始化的minLen变量没有改变过,说明不存在覆盖子串
        return minLen == Integer.MAX_VALUE ? "" : s.substring(ansLeft, ansRight + 1);
    }

    /**
     * 根据当前的slide和original数组中的频次来判断是否满足全覆盖
     *
     * @param tChars 需要覆盖的字符组
     * @return 完成覆盖返回true, 否则返回false
     */
    private boolean check(char[] tChars) {

        // 遍历original数组中各字符的频数,若每个字符的频数都不小于slide数组中相对应的字符的频数,则表明完成覆盖
        for (char c : tChars) {
            if (slide[c] < original[c]) {
                return false;
            }
        }
        return true;

    }
}