【优选算法必刷100题】第013题（同向双指针：滑动窗口算法）：水果成篮问题

艾莉丝努力练剑

发布于 2025-11-18 13:21:13

860

文章被收录于专栏：C / C++C / C++

013 水果成篮

力扣链接：904. 水果成篮

力扣题解链接：滑动窗口+数组模拟哈希表解决

题目描述：

1.1 解法：滑动窗口——算法思路

研究的对象是一段连续的区间，可以使用「滑动窗口」思想来解决问题。

让滑动窗口满足：窗口内水果的种类只有两种。

做法：右端水果进入窗口的时候，用哈希表统计这个水果的频次。这个水果进来后，判断哈希表的

大小——

（1）如果大小超过2：说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口，直到哈希表的大小小于等于2，然后更新结果；（2）如果没有超过2，说明当前窗口内水果的种类不超过两种，直接更新结果ret。

1.2 算法流程

1、初始化哈希表hash来统计窗口内水果的种类和数量；

2、初始化变量：左右指针left=0，right=0，记录结果的变量ret=0；

3、当right小于数组大小的时候，一直执行下列循环——

（1）将当前水果放入哈希表中；

（2）判断当前水果进来后，哈希表的大小：

[1] 如果超过2—— 1）将左侧元素滑出窗口，并且在哈希表中将该元素的频次减一； 2）如果这个元素的频次减一之后变成了0，就把该元素从哈希表中删除； 3）重复上述两个过程，直到哈希表中的大小不超过2；

（3）更新结果 ret；

（4）right++，让下一个元素进入窗口；

4、循环结束后，ret存的就是最终结果。

1.3 算法实现

1.3.1 第一次猛攻：失败

代码演示如下——

//自己实现，战败
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //hash表
        unordered_map<int, int> hash;
        //返回结果
        int ret = 0;
        //统计窗口内的水果类型和单一水果类型对应的水果数量
        for (int left = 0, right = 0; right < fruits.size(); right++)
        {
            hash[fruits[right]]++;//进窗口
            if (hash.size() > 2)
                hash[fruits[left]]--;//出窗口
            //小细节
            if (hash[fruits[right]] == 0)
                erase(hash[fruits[right]]);
            fruits[left]++;//left可以继续右移
            //更新结果
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)。

1.3.2 使用容器实现

代码演示如下——

//还是可以再优化，hash表频繁插入删除，时间复杂度虽然好，但还是比较耗时的
//可以进行小优化，针对的就是hash表
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //hash表
        unordered_map<int, int> hash;
        //返回结果
        int ret = 0;
        //统计窗口内的水果类型和单一水果类型对应的水果数量
        for (int left = 0, right = 0; right < fruits.size(); right++)
        {
            hash[fruits[right]]++;//进窗口
            while (hash.size() > 2)
            {
                //出窗口
                hash[fruits[left]]--;
                //小细节
                if (hash[fruits[left]] == 0)
                    hash.erase(fruits[left]);
                left++;//left可以继续右移
            }
            //更新结果
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)。

这里虽然时间复杂度良好，但是这种写法频繁地在hash表插入/删除一个元素，虽然时间复杂度是O(N)，但是还是比较耗时的。

1.3.3 优化：使用数组模拟哈希表——投机取巧

数量级是10^5，我们可以直接用数组模拟哈希表——

代码演示如下——

//优化了hash表之后，提高效率的一种做法
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //hash表
        unordered_map<int, int> hash;
        //返回结果
        int ret = 0;
        //统计窗口内的水果类型和单一水果类型对应的水果数量
        for (int left = 0, right = 0; right < fruits.size(); right++)
        {
            hash[fruits[right]]++;//进窗口
            while (hash.size() > 2)
            {
                //出窗口
                hash[fruits[left]]--;
                //小细节
                if (hash[fruits[left]] == 0)
                    hash.erase(fruits[left]);
                left++;//left可以继续右移
            }
            //更新结果
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};