力扣904水果成篮超时

Question

代码仅有一个测试用例不通过，原因是超出时间限制。
代码的时间复杂度为O(n)与题解一致

class Solution {
    public int totalFruit(int[] fruits) {
        int left = 0;
        int right = 0;
        int maxSum = 0;
        for (right = 0; right < fruits.length; right++) {
            int left2 = left;
            while (fruits[left] == fruits[left2]) {
                if (left2 == fruits.length - 1) {
                    maxSum = left2 - left + 1;
                    return maxSum; 
                } else {
                    left2++;
                }
            }
            if (fruits[right] == fruits[left] || fruits[right] == fruits[left2]) {
                maxSum = Math.max(maxSum, right - left + 1);
            } else {
                left = right - 1;
                while (fruits[left] == fruits[left - 1]) {
                    left--;
                }
            }
        }
        return maxSum;
    }
}

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

解答

力扣904水果成篮超时问题

问题描述：给定一个整数数组 fruits，其中的每个元素表示一种水果的数量。返回可以摘取的最多水果的数量。

你的代码的时间复杂度为 O(n)，与题解一致，但是仍然超出时间限制。这个问题的关键是如何快速地统计水果的种类和数量。

一个简单的解决方案是使用 HashMap 来统计水果的种类和数量，然后遍历数组，统计每种水果的数量。时间复杂度为 O(n)，空间复杂度为 O(1)。

以下是修改后的代码：

class Solution {
    public int totalFruit(int[] fruits) {
        if (fruits == null || fruits.length == 0) {
            return 0;
        }
        int maxCount = 0;
        int start = 0;
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int end = 0; end < fruits.length; end++) {
            countMap.put(fruits[end], countMap.getOrDefault(fruits[end], 0) + 1);
            while (countMap.size() > 2) {
                countMap.put(fruits[start], countMap.get(fruits[start]) - 1);
                if (countMap.get(fruits[start]) == 0) {
                    countMap.remove(fruits[start]);
                }
                start++;
            }
            maxCount = Math.max(maxCount, end - start + 1);
        }
        return maxCount;
    }
}

这个代码使用了两个指针 start 和 end，start 指向当前窗口的开始，end 指向当前窗口的结束。countMap 用于统计水果的种类和数量。遍历数组时，如果水果的种类超过 2 个，我们就将窗口向右移动，直到水果的种类不超过 2 个。然后，我们更新 maxCount 的值。

这个代码的时间复杂度为 O(n)，空间复杂度为 O(1)。