Java C++题解leetcode904水果成篮

题目描述：

在一个篮子里，你可以放入任意数量的水果，但是你只能放两种水果。篮子里的水果数量是无限的，你能够选择任意两种蔬菜放入篮子中。为了使你的成本最小，请输出你可以收集到的最大水果数。

示例 1:

输入: [1,2,1]
输出: 3
解释:我们可以收集 [1,2,1]。

示例 2:

输入: [0,1,2,2]
输出: 3
解释:我们可以收集 [1,2,2]。
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。

思路：

这是一道滑动窗口题目，要求滑动窗口中只包含两种元素，而这两种元素就是我们要找到的蔬菜。我们需要维护一个窗口，使得窗口内只有两种元素并且窗口大小尽可能大。我们可以使用哈希表（map或unordered_map）来存储窗口内每种元素的数量，如果我们发现窗口内元素数量大于2，则需要缩小窗口。我们可以通过移动左窗口指针来达到缩小窗口的目的。

步骤：

1.定义哈希表来记录窗口内每个元素出现的次数。

2.遍历元素，维护窗口的大小。

3.当窗口内元素数量大于2，则移动左窗口指针，直到窗口内元素数量为2。

4.更新最大蔬菜数量的值。

下面是Java语言的实现代码：

public int totalFruit(int[] tree) {
    int n = tree.length;
    if (n < 3) {
        return n;
    }

    Map<Integer, Integer> map = new HashMap<>();
    int i = 0, j = 0, max = 0;
    while (j < n) {
        int c = tree[j++];
        map.put(c, map.getOrDefault(c, 0) + 1);

        while (map.size() > 2) {
            int d = tree[i++];
            int count = map.get(d);
            if (count == 1) {
                map.remove(d);
            } else {
                map.put(d, count - 1);
            }
        }
        max = Math.max(max, j - i);
    }
    return max;
}

示例说明：

例如输入：[0,1,2,2]，我们需要维护一个大小为2的窗口。在初始状态下，窗口内没有元素，左右指针都指向数组的第一个元素。当我们移动右指针到第二个元素时，窗口包含两种元素[0, 1]，此时更新最大蔬菜数量的值为2。

接下来移动右指针到第三个元素，此时窗口包含三种元素[0, 1, 2]，此时需要移动左指针，直到窗口只包含两种元素[1, 2]。此时最大蔬菜数量的值为2。

继续移动右指针到第四个元素，此时窗口包含两种元素[2, 1]，更新最大蔬菜数量的值为3。窗口内的蔬菜数量为3，是目前找到的最大值，因此返回3。