当前位置：首页 > article >正文

2.5 滑动窗口专题：水果成篮

article 2025/3/16 17:01:38

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 次操作）。	需处理哈希表的动态更新，对边界条件敏感（如全为同一类型的数组）。