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

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
Solution: 本题使用滑动窗口思想，窗口内的元素和sum与目标target进行比较，如果满足要求，则更新当前最短的结果子数组长度，并且窗口左指针向右移动，试图寻找更短的子数组；一旦窗口元素和小于target，那么尝试右移右指针，重新寻找满足要求的子数组。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0, i = 0, j = i, result = Integer.MAX_VALUE;
        for (; i < nums.length; ++i) {
            sum += nums[i];
            while (sum >= target) {
                if (i - j + 1 < result) result = i - j + 1;
                sum -= nums[j++];
            }
        }
        return (result != Integer.MAX_VALUE) ? result : 0;
    }
}

904. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
Solution: 本题略为复杂，下面展示两种解法。
解法一： 使用双指针滑动窗口，开始指针st和结束指针end，窗口范围内是可摘的水果，fruit1和fruit2分别代表当前采摘水果类型，count1和count2分别代表两种类型水果当前采摘数量。当end向右移动时，有三种情况：

1. end指向水果为fruit1或者fruit2，说明当前水果可摘，那么对应的数量+1。
2. fruit1和fruit2至少一个为空（此处记为-1），说明新的可摘水果类型来到，那么将end指向水果填入，对应count置为1。
3. fruit1和fruit2均不为空， 且end指向第三种水果（非fruit1或fruit2），那么需要从原来两种水果类型中删去一种，秉持数量最大原则，这里将st右移，并依次将st指向的水果类型对应采摘数量-1，直到某一水果采摘数量（count1或count2）为0为止，此时置对应的水果类型为空，然后重新指向end代表的水果并将对应数量置为1，则窗口内仍然只有两种水果。

注意，在每次进入情况三的处理之前，需要计算窗口大小来更新当前最大采摘水果数量，而最后返回的是max(ans, end - st + 1) - 1是因为end遍历结束时窗口超出数组一个位置。 同时，这里的情况2可以合并到情况3处理完成后，因为它们都需要填入新水果类型。

class Solution {
    public int totalFruit(int[] fruits) {
        int fruit1 = -1, fruit2 = -1, count1 = 0, count2 = 0;
        int st = 0, end = 0, ans = 0;
        for (end = 0; end < fruits.length; ++end) {
            if (fruit1 == fruits[end]) ++count1;
            else if (fruit2 == fruits[end]) ++count2;
            else {
                if (fruit1 != -1 && fruit2 != -1) {
                    ans = Math.max(ans, end - st + 1);
                    while (st < end && count1 > 0 && count2 > 0) {
                        if (fruits[st] == fruit1) --count1;
                        else if (fruits[st] == fruit2) --count2;
                        if (count1 == 0) fruit1 = -1;
                        else if (count2 == 0) fruit2 = -1;
                        ++st;
                    }
                }
                if (fruit1 == -1) {
                    fruit1 = fruits[end];
                    count1 = 1;
                } else {
                    fruit2 = fruits[end];
                    count2 = 1;
                }
            }
        }
        return Math.max(ans, end - st + 1) - 1;
    }
}

解法二： 同滑动指针，与解法一的区别在于，删去count1和count2，在情况三中对st的右移改为从st = end - 1处左移，直到st和st - 1指向不同类型水果为止，由于窗口内始终只有两种水果，此时就意味着st - 1指向的水果将被抛弃，新的水果类型是fruits[st]和fruits[end]，这样做避免了从左到右移动st的冗余以及额外的count计数，降低了耗时。另外由于不需要count来计数，那么剩余情况只剩下：

1. 某一种采摘水果类型为空，则填入fruits[end]。
2. 两种采摘水果类型均不为空，且fruits[end]是新的类型，那么左移st直到找到要抛弃的水果类型，并更新当前采摘水果类型为fruits[st]和fruits[end]。

class Solution {
    public int totalFruit(int[] fruits) {
        int st = 0, end = 0;
        int fruit1 = -1, fruit2 = -1;
        int ans = 0;
        while(end < fruits.length){
            if (fruit1 == -1){
                fruit1 = fruits[end];
            } else if (fruit2 == -1 && fruits[end] != fruit1) {
                fruit2 = fruits[end];
            } else if (fruits[end] != fruit1 && fruits[end] != fruit2) {
                ans = Math.max(ans, end - st + 1);
                st = end - 1;
                while (fruits[st] == fruits[st - 1]){
                    --st;
                }
                fruit1 = fruits[st];
                fruit2 = fruits[end];
            }
            ++end;
        }
        return Math.max(ans, end - st + 1) - 1;
    }
}

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

Solution: 使用双指针，首先遍历字符串t，保存其各个字符出现频率count（此处由于字符数量有限，可用哈希表也可直接用数组），来表示当前窗口满足要求所需要的各个字符频率，并保存t的总长度记为t_num，用于记录当前窗口满足要求所需要的字符数量。
然后使用双指针遍历字符串s，右指针不断向右移动，每遇到一个字符则对应count减去1（该字符进入了窗口）。如果该字符频率在-1后仍然≥0，说明这个字符是窗口满足要求所需要的，应该从t_num中减去1，否则该字符是多余的，不需要动t_num。
如果t_num变为0，那么当前窗口内字符串已经满足要求，更新最优覆盖子串的位置，并且开始右移左指针，遇到的字符其count+1（因为该字符离开了窗口）。如果该字符频率在+1后>0，那么窗口内该字符数量不够了，需要将t_num加上1，否则窗口内该字符数量足够，不需要动t_num。一旦t_num不再为0，那么当前窗口不满足要求，需要回到右指针的右移过程。
注意： 如果使用哈希表存储count，那么在增减count之前需要判断指针指向的字符是否在表内，以避免无关字符进入表内，增加无谓空间消耗；如果使用数组储存则不需要这一过程。实际上无论采用哪种储存方式，无关字符其实对整个过程都不产生影响，因为在右指针右移过程中，无关字符的频率不可能≥0，同样左指针右移时，无关字符频率也不可能>0。

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(), t_num = t.length();
        int[] count = new int[52];
        for (char x : t.toCharArray()) {
            ++count[getIdx(x)];
        }
        int best_l = 0, best_len = Integer.MAX_VALUE;
        for (int l = 0, r = 0; r < n; r++) {
            int idx_r = getIdx(s.charAt(r));
            if (--count[idx_r] >= 0) --t_num;
            while (t_num == 0) {
                if (r - l + 1 < best_len) {
                    best_l = l;
                    best_len = r - l + 1;
                }
                int idx_l = getIdx(s.charAt(l++));
                if (++count[idx_l] > 0) ++t_num;
            }
        }
        return (best_len == Integer.MAX_VALUE) ? "" : s.substring(best_l, best_l + best_len);
    }
    int getIdx(char x) {
        return x >= 'A' && x <= 'Z' ? x - 'A' + 26 : x - 'a';
    }
}