13.LeetCode 904. 水果成篮：从暴力枚举到滑动窗口的完美进阶
目录
1. 题目解析
2. 算法原理
3. 编写代码
3.1 哈希表做法
3.2 数组模拟哈希表做法（性能提升）
总结
哈喽大家好，今天我们来详细讲解 LeetCode 上的一道经典题目——904. 水果成篮。这道题本质上是一个求“最长子数组（元素种类不超过2）”的问题，非常适合用滑动窗口来解决。下面我们结合算法原理和代码实现来深入理解。
OJ链接：https://leetcode.cn/problems/fruit-into-baskets/description/
1. 题目解析
我们先来看一下题目的具体要求：
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] 这两棵树。
转化思路：
将题目转化为：找出一个最长的子数组的长度，子数组中不超过两种类型的水果。
2. 算法原理
针对这道题，我们可以采用以下两种解法：
解法一：暴力枚举 + 哈希表
基本思路是枚举所有可能的子数组，利用哈希表统计每种子数组中水果的种类数，如果超过2种则跳过，否则更新最大长度。这种方法的时间复杂度较高，不推荐在大数据量下使用。
解法二：滑动窗口
滑动窗口是解决这类子数组问题的利器。
核心步骤：
left = 0,right = 0（初始化左右指针）进窗口：右指针不断向右移动，将新元素纳入窗口。
判断：检查当前窗口内水果的种类是否超过2种。
① kinds 不变 -> right 不变
② kinds 交小 -> right 右移
出窗口：如果种类超过2，左指针右移，将左侧元素移出窗口，直到种类恢复到2以内。
更新结果：在每一步合法状态下，更新最大水果数。
图解示意：
场景1：
f = [1, 2, 3, 2, 2]当右指针移动到
3时，窗口内有[1,2,3]，种类变为3，需要收缩左边界。
场景2：
f = [1, 2, 1, 2, 3, 2, 3, 3]同样，当遇到第三种水果
3时，我们需要移动左指针left，直到窗口内只剩下两种水果。
3. 编写代码
根据上述算法原理，我们给出两种 Java 实现方式。
3.1 哈希表做法
这种方法思路直观，利用HashMap来统计窗口内水果的种类和数量。
class Solution { public int totalFruit(int[] fruits) { //用Hash表来统计窗口内水果的种类和数量 Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); int ret = 0;//最大数目 for(int left = 0, right = 0; right < fruits.length; right++){ //入窗口 int in = fruits[right]; hash.put(in, hash.getOrDefault(in, 0) + 1); //判断 while(hash.size() > 2){ //出窗口 int out = fruits[left]; hash.put(out, hash.get(out) - 1); if(hash.get(out) == 0){ hash.remove(out); } left++; } //更新结果 ret = Math.max(ret, right - left + 1); } return ret; } }注：频繁使用哈希表会导致用时较大，因为涉及到较多的哈希计算操作。
3.2 数组模拟哈希表做法（性能提升）
观察数据范围0 <= fruits[i] < fruits.length，我们可以用数组来替代哈希表，从而大幅提升时间效率。因为数组的索引访问是 O(1)的，且没有哈希冲突的开销。
class Solution { public int totalFruit(int[] fruits) { //用数组模拟Hash表来统计窗口内水果的种类和数量 int n = fruits.length; int[] hash = new int[n + 1]; int ret = 0;//最大数目 for(int left = 0, right = 0, kinds = 0; right < fruits.length; right++){ //入窗口 int in = fruits[right]; if(hash[in] == 0) kinds++; hash[in]++; //判断 while(kinds > 2){ //出窗口 int out = fruits[left]; hash[out]--; if(hash[out] == 0){ kinds--; } left++; } //更新结果 ret = Math.max(ret, right - left + 1); } return ret; } }总结
水果成篮是典型的滑动窗口模板题。我们在处理时，关键在于维护窗口内的状态（这里是水果的种类数kinds）。当使用数组代替哈希表时，利用了题目条件对数据范围进行了优化，使得时间效率大大提升。希望大家通过这道题能熟练掌握滑动窗口的解题套路。