904. 水果成篮（滑动窗口）-Toy模板网

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

一、题目

二、代码

一、题目

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 904. 水果成篮（滑动窗口）,牛客/力扣,哈希算法,算法

二、代码

题目实质：找出一个最长的子数组的长度，要求子数组中不超过两种类型的水果
哈希表+双指针

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int _MaxCount = INT_MIN;
        int _Sum = 0;//总的水果种类

        vector<int>FruitType(100001, 0);//存放水果的种类
        vector<int>FruitCount(100001, 0);//不同种类水果的数量
        for (int left = 0, right = 0; right < fruits.size(); right++)
        {
            ++FruitCount[fruits[right]];//进窗口，对应种类的水果数量+1
            if (FruitType[fruits[right]] == 0)//如果某种水果的数量是0
            {
                FruitType[fruits[right]] = 1;
                _Sum++;//总的水果种类+1
            }
            if (_Sum <= 2)
            {
                _MaxCount = max(_MaxCount, right - left + 1);//更新
                continue;
            }
            if (_Sum > 2)//判断,水果种类大于2
            {
                _MaxCount = max(_MaxCount, right - left);//更新（次数fruits[right]处是第3种类型，所以左闭右开）
                int mark = fruits[left];

                while (fruits[left] == mark)//left右移，将连续相同的种类出窗口
                {
                    ++left;
                    --FruitCount[fruits[left - 1]];
                }

                if (FruitCount[fruits[left - 1]] == 0)//当移动到某种类水果数量为0的时候
                {
                    FruitType[fruits[left - 1]] = 0;//将不存在对应的种类
                    --_Sum;//总的水果种类-1
                }
            }
        }
        return _MaxCount;
    }
};

改进：文章来源地址https://www.toymoban.com/news/detail-722489.html

class Solution {
public:
    int totalFruit(vector<int>& f) 
    {
        int _MaxCount = INT_MIN;
        unordered_map<int, int> hash;//下标表示水果的种类，存放某种类水果数量
        for (int left = 0, right = 0; right < f.size(); right++)
        {
            ++hash[f[right]];//进窗口
            while (hash.size() > 2)
            {
                //出窗口
                --hash[f[left]];//某种类水果数量-1
                if (hash[f[left]] == 0)//如果某种类水果数量为0，则删除该种类
                {
                    hash.erase(f[left]);
                }
                left++;
            }
            _MaxCount = max(_MaxCount, right - left + 1);
        }

        return _MaxCount;
    }
};

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