C++优选算法 904. 水果成篮

1.题目描述

看到这种题目，总觉得自己在做阅读理解，晕了，题目要求我们在一个数组里分别找出两种数字，并统计这两种数字分别出现一共是多少。

2.算法思路

采用哈希表+滑动窗口的做法：

• 定义一个哈希表方便存储，因为数组里面都是数字，将数组转换成下标可以准确的记录下来。
• 进窗口：如果哈希表存储大小不超过2，将其存储对应下标。
• 出窗口：如果哈希表存储大小超过2，使窗口向前移动，删除哈希表里对应的数字。
  

3.完整代码

容器做法

class Solution {
public:int totalFruit(vector<int>& fruits) {//容器做法unordered_map<int,int> hash;int left=0,right=0,ret=-1;for(;right<fruits.size();right++){//进窗口hash[fruits[right]]++;//判断while(hash.size()>2){//出窗口hash[fruits[left]]--;if(hash[fruits[left]]==0)hash.erase(fruits[left]);left++;}//更新ret = max(ret,right-left+1);}return ret;}
};

数组做法

class Solution {
public:int totalFruit(vector<int>& fruits) {//数组做法int hash[114514]={0};int left=0,right=0,ret=-1,kinds=0;for(;right<fruits.size();right++){//进窗口if(hash[fruits[right]]==0)kinds++;hash[fruits[right]]++;//判断while(kinds>2){//出窗口hash[fruits[left]]--;if(hash[fruits[left]]==0)kinds--;left++;}//更新ret = max(ret,right-left+1);}return ret;}
};