904.水果成篮

难度：中等

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

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

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

给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

1 <= fruits.length <= 10^(5)
0 <= fruits[i] < fruits.length

解题思路

感觉涉及到 连续区间查找 的题，似乎都可以考虑一下 滑动窗口 的思想。

直接套 滑动窗口模板：

java

/* 滑动窗口算法框架 */
void slidingWindow(String s) {
    // 用合适的数据结构记录窗口中的字符及其频率
    HashMap<Character, Integer> window = new HashMap<>();

    int left = 0, right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        window.put(c, window.getOrDefault(c, 0) + 1);
        ...
        // 判断窗口左侧是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            window.put(d, window.get(d) - 1);
            ...
        }
    }
}

我的思路：

设定两个指针，left 指向目标区间最左边的位置，right 寻找目标区间最右边的元素
设定一个哈希表 HashMap 作为窗口，用来存储当前篮子里的水果种类和数量信息，其中 key 为水果的种类，value 为该水果的数量（出现频率）
设定 maxCount 记录当前窗口内的水果数量最大值，初始为 0
在 right 的遍历过程中：
1. 暂存要移入窗口的水果
2. 增大窗口，也就是 right 右移一位
3. 对 HashMap 进行更新，将当前水果加入窗口中
4. 判断窗口左侧是否要收缩，若 HashMap 内水果种类大于 2，则说明要收缩窗口了：
  1. 暂存要移出窗口的水果
  2. 缩小窗口，也就是 left 右移一位
  3. 对 HashMap 进行更新，移除目标水果，若该水果的 value 为 0，则从 HashMap 中删掉其 key
5. 更新结果，left 指向目标窗口的首位，right 指向目标窗口的末尾+1的位置，所以 maxCount = Math.max(maxCount, right - left)
返回 maxCount 的值

我的代码

java

public int totalFruit(int[] fruits) {
    // 用合适的数据结构记录窗口中的字符及其频率
    HashMap<Integer, Integer> window = new HashMap<>();
    int left = 0;
    int right = 0;
    // 记录结果
    int maxCount = 0;

    while (right < fruits.length) {
        // c 是将移入窗口的字符
        int fruit = fruits[right];
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        window.put(fruit, window.getOrDefault(fruit, 0) + 1);
		// 判断窗口左侧是否要收缩
        while (window.size() > 2) {
            // d 是将移出窗口的字符
            int fruitToRemove = fruits[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            window.put(fruitToRemove, window.get(fruitToRemove) - 1);
            if (window.get(fruitToRemove) == 0) {
                window.remove(fruitToRemove);
            }  
        }
		// 在这里更新结果，left指向目标窗口的首位，right指向目标窗口的末尾+1的位置
        maxCount = Math.max(maxCount, right - left);
    }
    return maxCount;
}

时间复杂度：O(n)，虽然有双层循环，但其实每个元素最多被遍历两次

空间复杂度：O(1)

总结

一开始想到用哈希表来做，发现有问题。

后来采用滑动窗口来做，发现也有问题。

其实两种思想结合在一起，才是本问题的真正解法。

904.水果成篮 ​

解题思路 ​

我的代码 ​

总结 ​

904.水果成篮

解题思路

我的代码

总结