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

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插件快速发布