题目链接
力扣(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]]++;// 若此时种类大于2while(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,来减少空间的开辟,并且使用一个变量来记录当前的水果种类。
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++;// 若此时种类大于2while(count>2){// 出窗口hash[f[left]]--;// 如果当前种类的水果已经减为0了,那么应该删除该元素if(hash[f[left]]==0) count--;// 更新窗口left++;}// 更新结果ret=max(ret,right-left+1);}return ret;}
};