1. 题目链接
leecode 904.水果成篮
2. 题目描述
给定一个整数数组 fruits，每个元素表示一棵树上的水果类型。你只能收集两种不同类型的水果，且必须从任意位置开始按顺序连续收集。
目标：返回能收集水果的最大数量（即最长子数组长度）。
示例：
输入：fruits = [1,2,3,2,2]
输出：4（子数组 [2,3,2,2]，包含两种类型：2 和 3）。
作者说：
由于这里的题目比较难以理解，我给出我的理解：从数组 fruits 中找到一个最长子串，该字串中最多只有两个重复的数字。
3. 算法思路
滑动窗口法：
- 核心思想：维护一个窗口，窗口内最多包含两种不同的水果类型。
- 哈希表记录状态：用
unordered_map统计窗口内各类型的数量。 - 动态调整窗口：
- 右指针扩展：将当前水果加入窗口。
- 左指针收缩：当窗口内类型超过 2 时，左指针右移，直到窗口合法。
- 实时更新结果：每次窗口调整后计算当前窗口长度，更新最大值。
暴力枚举法：
- 核心思想：遍历所有可能的子数组，检查是否满足最多两种类型。
- 双重循环嵌套：枚举子数组的起点
i和终点j。 - 类型统计：对每个子数组维护类型集合，当类型超过 2 时终止内层循环。
4. 代码实现
class Solution
{
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();int left = 0, right = 0,ret = 0;unordered_map<int,int> hash;while(right < n){// 扩展右窗口hash[fruits[right]]++;// 收缩左窗口while(hash.size() > 2 ){hash[fruits[left]]--;if(hash[fruits[left]] == 0)hash.erase(fruits[left]);left++;}// 更新结果ret = max(ret, right - left + 1);right++;}return ret;}
};
5. 暴力枚举法与滑动窗口法对比图表
| 对比维度 | 暴力枚举法 | 滑动窗口法 |
|---|---|---|
| 核心思想 | 遍历所有子数组，逐一检查是否包含最多两种类型。 | 动态维护窗口，保证窗口内始终包含最多两种类型。 |
| 时间复杂度 | O(n²)（枚举所有起点和终点，类型检查优化后为 O(n²)）。 | O(n)（每个元素被左右指针各访问一次）。 |
| 空间复杂度 | O(1) 或 O(2)（维护一个固定大小的集合记录类型）。 | O(2)（哈希表最多存储两种类型）。 |
| 实现方式 | 双重循环枚举起点和终点，内层循环统计类型。 | 单层循环扩展右指针，内层循环收缩左指针。 |
| 适用场景 | 小规模数据（n ≤ 1e3）。 | 大规模数据（n ≤ 1e5）。 |
| 优点 | 逻辑简单，易于实现。 | 时间复杂度最优，适用于大规模数据。 |
| 缺点 | 数据规模大时性能极差（n=1e4 时需 1e8 次操作）。 | 需处理哈希表的动态更新，对边界条件敏感（如全为同一类型的数组）。 |
6. 边界条件与注意事项
- 全为一种类型：滑动窗口直接返回
n（例如fruits = [2,2,2]）。 - 交替类型：如
fruits = [1,2,1,2,1]，窗口会动态调整，始终保留两种类型。 - 哈希表维护：当类型数量减到 0 时需及时删除键值，避免
hash.size()误判。
7. 总结
- 滑动窗口法是本题的最优解，时间复杂度为 O(n)，适用于大规模数据。
- 暴力枚举法仅用于验证算法正确性或处理极小数据规模。