904. 水果成篮（滑动窗口）

目录

一、题目

二、代码

---

一、题目

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

二、代码

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

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;
    }
};

改进：

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;
    }
};