滑动窗口是数组题目中常见的算法。通常可以把 O(n^2) 的复杂度变成 O(n)。滑动窗口适合「在数组中求一个连续的子数组」之类的题目。

要使用滑动窗口，需要考虑三个条件：

1. 窗口内是什么？
   一般要保证窗口内是满足题意的子数组（首次达成题意之前除外）。

2. 窗口结束位置何时移动？
   有两个情形需要扩大窗口：

   1. 当前窗口未满足题意，需要尝试更多元素时。
   2. 当前已经满足题意，吸纳下一个元素后依然可以满足题意。

3. 窗口启始位置何时移动？
   同样有两个情形需要收缩窗口：

   1. 右侧已到达边缘。
   2. 吸纳下一个元素则窗口不再满足题意，必须先扔掉一些元素。

基础-209 长度最小的子数组

传送门

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

根据题目与上门的总结，可以得出相关的边界条件：

• 扩大窗口：当前窗口内 sum 值小于 target。（未满足题意，需要尝试更多元素）。注意如果目前 sum>=target 就不能继续扩大了，因为题目希望找最短数组，继续扩大后明显违背题意。
• 收缩窗口： 目前 sum>=target（吸纳下一个元素则窗口不再满足题意） 或右侧已到数组边缘。

比较简单，直接上答案（java）：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = nums.length + 1;
        int sum = 0;
        int l = 0, r = -1; // [l,r] 为窗口，因为是闭区间，所以 r 初始化为 -1 表示没有元素
        while (l < nums.length) {
            if (r + 1 < nums.length && sum < target) { // 扩大窗口
                r++;
                sum += nums[r];
            } else { // 收缩窗口
                sum -= nums[l];
                l++;
            }
            if (sum >= target) { // 记录可能的答案
                result = Math.min(result, r - l + 1);
            }
        }
        if (result == nums.length + 1)
            result = 0;
        return result;
    }
}

904-装水果

传送门

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

这个问题描述的比较生活化，首先要抽象出模型。我的总结是：给定一个数组，元素表示类型。寻找最长的子数组，要求其只能包含至多 2 种类型。

「寻找最长的子数组」显然可以考虑滑动窗口。边界条件如下：

• 扩大窗口：下一个元素在已经选中的类型之中，或仍有新类型的名额。（因为题目要求寻找尽可能大，因此永远不能满足题意）
• 缩小窗口：下一个元素是新类型，且已经没有额外的名额。

分析出了这些，答案也就呼之欲出了：

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int totalFruit(int[] fruits) {
        int result = 0;
        int num = 0;
        Map<Integer, Integer> collected = new HashMap<>(); // type -> num
        int l = 0, r = -1; // [l,r]
        while (l < fruits.length) {
            if (r + 1 < fruits.length &&
                    (collected.size() < 2 || collected.containsKey(fruits[r + 1]))) {
                r++;
                collected.put(fruits[r], collected.getOrDefault(fruits[r], 0) + 1);
                num++;
            } else {
                collected.put(fruits[l], collected.get(fruits[l]) - 1);
                num--;
                if (collected.get(fruits[l]) == 0)
                    collected.remove(fruits[l]);
                l++;
            }
            result = Math.max(result, num);
        }
        return result;
    }
}

与上一题的区别是，舍掉一个元素，不见得一定会空出新的坑位。因此需要记录每个类型已经收集的个数，归零时才能视为真正舍掉。

76-最小覆盖子串

传送门

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

字符串可以看作数组，最小字串就是最小子数组。因此可以考虑使用滑动窗口。

要包含的内容是一个未知长度的字符数组，所以我们要使用一个数据结构记录并可以快速查找已经包含了哪些字符。同时字符可以重复，那么就不可以使用 Set，只能选择 Map。不过这里限制了只会是英文字符，简单起见使用一个 int[127]，每一个元素表示这个字符需要出现多少次。初始化这个数组：

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

但这个数据结构不能快速判断当前子串是否符合题意（需要遍历每个元素是否 <=0 才行），那么就再用一个额外的 int 变量记录还有多少个字符需要包含。归零时表示已经满足题意。下面我们只要维护 table 和这个计数器即可，这也是这道题难度所在。

来确定边界条件：

• 扩大窗口：计数器未归零。（当前窗口未满足题意，需要尝试更多元素）
• 收缩窗口：计数器已经归零。（吸纳下一个元素则窗口不再满足题意，因为不是最小子串了）

完整代码：

class Solution {
    public String minWindow(String s, String t) {
        int[] table = new int[127];
        int nums = t.length();
        for (int i = 0; i < t.length(); i++)
            table[t.charAt(i)]++;
        int l = 0, r = -1;
        String result = "";
        while (l < s.length()) {
            if (r + 1 < s.length() && nums > 0) {
                r++;
                table[s.charAt(r)]--;
                if (table[s.charAt(r)] >= 0)
                    nums--;
            } else {
                table[s.charAt(l)]++;
                if (table[s.charAt(l)] > 0)
                    nums++;
                l++;
            }
            if (nums == 0 && (result.isEmpty() || r - l + 1 < result.length()))
                result = s.substring(l, r + 1);
        }
        return result;
    }
}

维护 table 和计数器的难点在于：

• 每当吸纳一个元素时，不能直接递减计数器。因为有这样一种可能：这个字符本来就不要求包含。若全部递减计数器，则计数器归零不再能代表当前字串已满足题意。比如：

  s="aaaa"
  t="eeee"
  若不加判断，循环执行完毕后，状态是 table['a']=-4, table['e']=4, nums=0
  最后程序返回 "aaaa"，答案错误

• 同理，舍掉一个元素时，也不能直接递增计数器。

为解决这个问题，可以找到一个规律：只有 table 中递减后的值 >=0 的元素才是要求包含的。其他元素在处理时就不必更新计数器。舍掉递增计数器时同理：只有 table 中递增后的值 >0 的元素是要求包含的。

搞清楚了这个，这道题即可顺利解决。