76. 最小覆盖子串

滑动窗口

import java.util.Arrays;

class Solution {
    public String minWindow(String s, String t) {

        if (s.length() < t.length()){
            return "";
        }
        /**
         * 滑动窗口
         * 用哈希表数组记录t中每个字符在s中是否出现
         * 右指针right一直右移，直到满足条件，然后记录下此时区间的边界，如果长度更小则更新l和r
         */
        int[] tCount = new int[128];
        int right = -1;
        int l = 0;
        int r = -1;

        for (int i = 0; i < t.length(); i++) {
            tCount[t.charAt(i)]++;
        }

        /**
         * 左指针i从0开始，只有当区间包含所有t的字符后才会移动
         */
        for (int i = 0; i < s.length() - t.length() + 1; i++) {

            /**
             * 只要区间没有完全包含t的元素，右指针right就不断移动
             * 同时right不能越界
             * 每次循环都要找出数组的最大值，时间复杂度为O(n^2)
             */
            while (Arrays.stream(tCount).max().getAsInt() > 0 && right < s.length() - 1){

                right++;
                tCount[s.charAt(right)]--;
            }

            /**
             * 只有当包含t的所有字符且区间长度更小且r < l时才会更新
             */
            if (Arrays.stream(tCount).max().getAsInt() == 0) {

                if (r < l) {

                    r = right;
                    l = i;
                }
                else if (r - l + 1 > right - i + 1){

                    r = right;
                    l = i;
                }
            }

            /**
             * 在左指针移动之前，要抛弃掉当前字符
             */
            tCount[s.charAt(i)]++;
        }

        return s.substring(l, r + 1);
    }
}

/**
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(1)
 */

优化1——不用每次都找出数组最大值，同时简化判断条件

import java.util.Arrays;

class Solution {
    public String minWindow(String s, String t) {

        if (s.length() < t.length()){
            return "";
        }
        /**
         * 滑动窗口
         * 用哈希表数组记录t中每个字符在s中是否出现
         * 右指针right一直右移，直到满足条件，然后记录下此时区间的边界，如果长度更小则更新l和r
         */
        int[] tCount = new int[128];
        int num = t.length();
        int right = -1;
        int l = 0;
        int r = -1;

        for (int i = 0; i < t.length(); i++) {
            tCount[t.charAt(i)]++;
        }

        /**
         * 左指针i从0开始，只有当区间包含所有t的字符后才会移动
         */
        for (int i = 0; i < s.length() - t.length() + 1; i++) {

            /**
             * 只要区间没有完全包含t的元素，右指针right就不断移动
             * 同时right不能越界
             * 使用一个变量num同步记录t中字符出现的次数，当次数大于0时才减1，这样就不用每次都比较tCount的最大值了
             */
            while (num > 0 && right < s.length() - 1){

                right++;

                if (tCount[s.charAt(right)] > 0) {
                    num--;
                }

                tCount[s.charAt(right)]--;
            }

            /**
             * 只有当包含t的所有字符且区间长度更小且r < l时才会更新
             */
            if (num == 0 && (r < l || r - l + 1 > right - i + 1)) {
                
                r = right;
                l = i;
            }

            /**
             * 在左指针移动之前，要抛弃掉当前字符，同时维护num
             * 如果这个字符的次数是负数，说明其不在t中，num就不用更新
             */
            if (tCount[s.charAt(i)] == 0) {
                num++;
            }

            tCount[s.charAt(i)]++;
        }

        return s.substring(l, r + 1);
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

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