LeetCode 904. 水果成篮-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 904. 水果成篮。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

LeetCode 904. 水果成篮,算法练习,leetcode,算法

题目解析

在你去摘水果的时候，你当前只能拥有两种种类的水果，若想拿第三种水果，就需要发下前两种水果中的一种。

法一：滑动窗口+哈希表(未优化版本)

我们使用哈希表来记录当前水果出现的次数，当哈希表中已经有两种水果的时候，下次再摘第三种水果，就应该将前面的水果进行拿出，直到当前种类恢复到两种为止。使用滑动窗口思想，遍历到之后就进窗口，当种类超过2时就从左边进行出窗口，然后每次遍历的结尾去获取最长的子串长度。

class Solution 
{
public:
    int totalFruit(vector<int>& f) 
    {
        int n=f.size();
        int ret=INT_MIN;
        // 定义一个哈希表
        unordered_map<int,int> hash;
        for(int left=0,right=0;right<n;right++)
        {
            // 进窗口
            // 记录当前水果和增加该水果出现的次数
            hash[f[right]]++;
            // 若此时种类大于2
            while(hash.size()>2)
            {
                // 出窗口
                hash[f[left]]--;
                // 如果当前种类的水果已经减为0了，那么应该删除该元素
                if(hash[f[left]]==0)
                hash.erase(f[left]);
                // 更新窗口
                left++;
            }
            // 更新结果
            ret=max(ret,right-left+1);
        }
        return ret;
    }
};

法二：滑动窗口+哈希表(优化版本)

我们利用一个数组来代替unordered_map，来减少空间的开辟，并且使用一个变量来记录当前的水果种类。文章来源地址https://www.toymoban.com/news/detail-697813.html

class Solution 
{
public:
    int totalFruit(vector<int>& f) 
    {
        int n=f.size();
        int ret=INT_MIN;
        // 定义一个哈希表
        int hash[100001]={0};
        for(int left=0,right=0,count=0;right<n;right++)
        {
            // 进窗口
            // 记录当前水果和增加该水果出现的次数
            hash[f[right]]++;
            if(hash[f[right]]==1) count++;
            // 若此时种类大于2
            while(count>2)
            {
                // 出窗口
                hash[f[left]]--;
                // 如果当前种类的水果已经减为0了，那么应该删除该元素
                if(hash[f[left]]==0) count--;
                // 更新窗口
                left++;
            }
            // 更新结果
            ret=max(ret,right-left+1);
        }
        return ret;
    }
};

到了这里，关于LeetCode 904. 水果成篮的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！