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

水果成篮（滑动窗口）"/>

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]];//进窗口，对应种类的水果数量+1if (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]];//某种类水果数量-1if (hash[f[left]] == 0)//如果某种类水果数量为0，则删除该种类{hash.erase(f[left]);}left++;}_MaxCount = max(_MaxCount, right - left + 1);}return _MaxCount;}
};