题目

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

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

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

举例： 输入：fruits = [1,2,3,2,2] 输出：4

题解

滑动窗口解法

这题应该用滑动窗口解法。首先有左右两个指针 和一个map。 右侧指针先走，并记录下当前水果的种类和数量。当种类大于2时，我们需要移动左指针并且更新种类数量，当种类数量为0时，要删除该种类。 在遍历过程中用right-left+1 表示当前的结果。这些结果中取最大的结果即可。

var totalFruit = function (fruits) {
    let ans = 0;
    let left = 0;

    var map = new Map()
    for (let right = 0; right < fruits.length; right++) {
        map.set(fruits[right], (map.get(fruits[right]) ?? 0) + 1)


        while (map.size > 2) {
            const currentLeft = fruits[left]
            let currentLeftValue = map.get(currentLeft)
            //move left
            map.set(currentLeft, --currentLeftValue)

            if (currentLeftValue === 0) {
                map.delete(currentLeft)
            }

            ++left;
        }
        //console.log('left:', left, 'rgiht', right)
        ans = Math.max(ans, right - left + 1)
    }

    return ans
};

从暴力法来说，很简单，需要两个循环。第一次循环就是从每一个位置开始，第二层循环是判断当前的最大可选。

var totalFruitBaoli = function (fruits) {
    let maxFruit = 0;
    for (let i = 0; i < fruits.length; i++) {
        var result = testCurrentHead(fruits, i)
        maxFruit = maxFruit > result ? maxFruit : result
    }
    return maxFruit
};

var testCurrentHead = function (fruits, start) {
    var set = new Set()
    var result = 0
    for (let i = start; i < fruits.length; i++) {
        if (set.has(fruits[i])) {
            result++;
        } else {
            set.add(fruits[i]);
            if (set.size > 2) {
                break;
            } else {
                result++;
            }
        }
    }
    return result;
}