双指针与滑动窗口中等1 种解法

#904水果成篮

寻找只包含至多两种值的最长连续子数组，对应两个篮子可采摘的最多水果数。

#数组#哈希表#滑动窗口

解题主线

题意等价于至多包含两种水果的最长连续窗口。

频次表记录窗口内每种水果的数量；类型超过两种时从左侧收缩，频次归零后删除键。

窗口恢复合法后，right - left + 1 就是以当前右端结尾的最长合法区间。

解法 1：至多两类的滑动窗口

右端加入水果并更新频次；种类超过两种时移动左端并清理零频次，持续更新合法窗口最大长度。

时间复杂度

O(n)

空间复杂度

O(1)，窗口内至多维护 3 种水果

904. 水果成篮 · 至多两类的滑动窗口

java

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

final class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> counts = new HashMap<>();
        int left = 0;
        int maximum = 0;

        for (int right = 0; right < fruits.length; right++) {
            counts.merge(fruits[right], 1, Integer::sum);
            while (counts.size() > 2) {
                int removed = fruits[left++];
                int remaining = counts.get(removed) - 1;
                if (remaining == 0) counts.remove(removed);
                else counts.put(removed, remaining);
            }
            maximum = Math.max(maximum, right - left + 1);
        }
        return maximum;
    }
}

右端加入水果并更新频次；种类超过两种时移动左端并清理零频次，持续更新合法窗口最大长度。

边界与易错点

必须连续从一排树中采摘，不能任选全局出现最多的两种水果。
频次减到 0 时要删除键，否则 basket.size() 不会恢复到 2。
旧注释称哈希表记录最后索引，实际实现记录的是频次；整理后统一语义。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q904_totalFruit.java