目录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以内。更新结果在每一步合法状态下更新最大水果数。图解示意场景1f [1, 2, 3, 2, 2]当右指针移动到3时窗口内有[1,2,3]种类变为3需要收缩左边界。场景2f [1, 2, 1, 2, 3, 2, 3, 3]同样当遇到第三种水果3时我们需要移动左指针left直到窗口内只剩下两种水果。3. 编写代码根据上述算法原理我们给出两种 Java 实现方式。3.1 哈希表做法这种方法思路直观利用HashMap来统计窗口内水果的种类和数量。class Solution { public int totalFruit(int[] fruits) { //用Hash表来统计窗口内水果的种类和数量 MapInteger, Integer hash new HashMapInteger, 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。当使用数组代替哈希表时利用了题目条件对数据范围进行了优化使得时间效率大大提升。希望大家通过这道题能熟练掌握滑动窗口的解题套路。