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

用户11915063

发布于 2025-11-20 13:10:53

160

水果成篮

题目链接：

904. 水果成篮 - 力扣（LeetCode）

题目描述：

题目示例：

解法（滑动窗口）：

算法思路：

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

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

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

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

算法流程：

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

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

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

将当前水果放入哈希表
判断当前水果进来后，哈希表的大小：

如果超过 2 ：

将左侧元素滑出窗口，并且在哈希表中将该元素的频次减一；

如果这个元素的频次减一之后变成了 0，就把该元素从哈希表中删除；

重复上述两个过程，直到哈希表中的大小不超过 2；

更新结果 ret；
right++，让下一个元素进入窗口；

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

C++代码演示：(容器版本)

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //数据范围有限可以使用数组模拟哈希表
        int hash[100001]={0};//后面需要加个kinds变量
        int n=fruits.size();
        int left=0,right=0,len=0;
        while(right<n)
        {
            if(hash[fruits[right]]==0) kinds++;//维护水果种类
            hash[fruits[right]]++;//进窗口
            while(kinds>2)//判断
            {
                hash[fruits[left]]--;//出窗口
                if(hash[fruits[left]]==0) kinds--;
                left++;
            }
            //更新结果
            len=max(len,right-left+1);
            right++;
        }
        return len;
    }
};

C++代码演示：(数组模拟哈希表版本)

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //数据范围有限可以使用数组模拟哈希表
        int hash[100001]={0};//后面需要加个kinds变量
        int n=fruits.size();
        int left=0,right=0,kinds=0,len=0;
        while(right<n)
        {
            if(hash[fruits[right]]==0) kinds++;//维护水果种类
            hash[fruits[right]]++;//进窗口
            while(kinds>2)//判断
            {
                hash[fruits[left]]--;//出窗口
                if(hash[fruits[left]]==0) kinds--;
                left++;
            }
            //更新结果
            len=max(len,right-left+1);
            right++;
        }
        return len;
    }
};

往期回顾：

【优选算法必刷100题】第009~010题（滑动窗口）：长度最小的子数串、无重复字符的最长字串

【优选算法必刷100题】第011~012题（滑动窗口）：最大连续1的个数 III，将 x 减到 0 的最小操作数

结语：本篇博客通过滑动窗口处理连续区间问题。当窗口内水果种类超过2种时，左指针右移调整窗口，利用哈希表统计频次，最终求出最大区间长度，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-12，如有侵权请联系 cloudcommunity@tencent.com 删除

数组