代码随想录-数组-滑动窗口

008 长度最小的子数组

Alt text

  • 思考:自然直觉是两层for循环遍历所有子数组,对每个子数组进行求和判断。能否使用一层for循环,减少一些不必要的子数组访问量? 滑动窗口思想:一层forj循环,其中j代表了子数组的end而不是start;
    1. j每移动一步,判断当前子数组是否满足要求(本题要求为子数组中的元素和大于等于target);
    2. 满足条件时:
      1. 更新长度:比较当前子数组长度和上一次记录的长度;
      2. 转而移动代表了子数组start的i,从而尽量缩短子数组长度,i的移动规则非常重要(本题中如果当前子数组的sum-[i]仍然>=target则i可以右移)
public static int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int sum = 0, res = Integer.MAX_VALUE, tmp = 0;
        for (int i = 0, j = 0; j < len; j++) {
            sum += nums[j];
            while (sum >= target) {
                tmp = j - i + 1;
                res = res < tmp ? res : tmp;
                if (res == 1) {
                    return res;
                }
                sum -= nums[i++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

904 水果成篮

Alt text

  • 思考:题意就是寻找最长的子数组,要求该子数组中最多仅包含两种数字。基于滑动窗口的思想,尝试使用一层forj,其中j为窗口end,但是几个条件很难构造,比如什么时候表明当前子数组满足要求,于是我按照比较自然的“流水式”的思想模拟过程:
    1. 初始将两种水果类型统一为数组第一个数;
    2. for循环中:
      1. 第一个if:当前[j]属于两种水果中的一种,那么j继续后移,更新长度;
      2. 第二个if:没进入第一个if,表明[j]不属于两种水果,那么如果当前两种水果是同一种,那可以让其中一种变成[j],j继续后移,更新长度;
      3. 第三个for:没进入前两个if,表明[j]遇到了第三种水果,关键来啦——这个时候两种水果种类应该怎么改变,首先毋庸置疑,其中一种必须变成[j],为了接下去得到尽量长的子数组,另一种应该就是[j-1],那么i怎么移动?自然就是从j-1开始倒序向前找到连续的最后一个[j-1]
public static int totalFruit(int[] fruits) {
        int len, tmp, res = 0;
        if ((len = fruits.length) == 0) {
            return res;
        }
        int t1 = fruits[0], t2 = t1;
        for (int i = 0, j = 0; j < len; j++) {
            if (fruits[j] == t1 || fruits[j] == t2) {
                tmp = j - i + 1;
                res = res > tmp ? res : tmp;
                continue;
            }
            if (t1 == t2) {
                t2 = fruits[j];
                tmp = j - i + 1;
                res = res > tmp ? res : tmp;
                continue;
            }
            for (i = j - 2; fruits[i] == fruits[j - 1]; i--) {
            }
            i++;
            t1 = fruits[j - 1];
            t2 = fruits[j];
        }
        return res;
    }

76 最小覆盖子串

Alt text

  • 思考:求最小子串,框架相比904而言更接近008,关键问题还是什么时候表明当前子数组满足条件,随后i的移动又有什么规则?
    1. 因为字符串仅包含字母,故用一个数组模拟hash;
    2. 非常关键的是,将数组的[0]用来表示当前t中等待匹配的字母的种类数,而非简单的个数,因此在初始化数组arr时和[j]属于t时都增加了if判断来对arr[0]进行修改;
    3. 那么自然的,当arr[0]==0时,表明当前t中待匹配字母种数为0,当前子数组已经涵盖了所有t中的字母;
    4. 如何移动i?当[i]不属于t时继续右移,另外,当[i]属于t但是当前子数组中[i]数量多于t中时,继续右移;
    5. 注意到,有两个地方在修改arr数组时没有紧跟if判断而决定是否修改arr[0]:
      1. 移动i的过程中,当[i]属于t但是当前子数组中[i]数量多于t中时,当前的[i]相当于是重复的、多余的,因此一定不影响待匹配的字母的种类数;
      2. i移动结束,[i-1]是使得子数组从满足条件变成不满足条件的关键元素,因此一定会影响待匹配的字母的种类数
    6. 另外,为什么我让arr长度为59大于实际使用的53,因为想要统一(-64),因此保留了A与a中间的空余
int len = t.length();
        int[] arr = new int[59];
        for (int i = 0; i < len; i++) {
            arr[t.charAt(i) - 64] += 1;
            if (arr[t.charAt(i) - 64] == 1) {
                arr[0] += 1;
            }
        }
        int start = 0, end = 0, tmp = 0, res = Integer.MAX_VALUE;
        for (int i = 0, j = 0; j < s.length(); j++) {
            if (t.indexOf(s.charAt(j)) != -1) {
                arr[s.charAt(j) - 64] -= 1;
                if (arr[s.charAt(j) - 64] == 0) {
                    arr[0] -= 1;
                }
            }
            while (arr[0] == 0) {
                for (; t.indexOf(s.charAt(i)) == -1 || arr[s.charAt(i) - 64] < 0; i++) {
                    if (arr[s.charAt(i) - 64] < 0) {
                        arr[s.charAt(i) - 64] += 1;
                    }
                }
                tmp = j - i + 1;
                if (tmp < res) {
                    start = i;
                    end = j;
                    res = tmp;
                }
                arr[s.charAt(i) - 64] += 1;
                arr[0] += 1;
                i++;
            }
        }
        if (tmp < len) {
            return "";
        } else {
            return s.substring(start, end + 1);
        }

本文章使用limfx的vscode插件快速发布