当前位置：首页 > news >正文

LeetCode 904. 水果成篮【不定长滑窗+哈希表】1516

news 2026/6/6 5:18:31

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组fruits表示，其中fruits[i]是第i棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组fruits，返回你可以收集的水果的最大数目。

示例 1：

输入：fruits=[1,2,1]输出：3解释：可以采摘全部3棵树。

示例 2：

输入：fruits=[0,1,2,2]输出：3解释：可以采摘[1,2,2]这三棵树。 如果从第一棵树开始采摘，则只能采摘[0,1]这两棵树。

示例 3：

输入：fruits=[1,2,3,2,2]输出：4解释：可以采摘[2,3,2,2]这四棵树。 如果从第一棵树开始采摘，则只能采摘[1,2]这两棵树。

示例 4：

输入：fruits=[3,3,3,1,2,1,1,2,3,3,4]输出：5解释：可以采摘[1,2,1,1,2]这五棵树。

提示：

1 <= fruits.length <= 10^5
0 <= fruits[i] < fruits.length

解法不定长滑窗+哈希表

找一个最长连续子数组，满足子数组中至多有两种数字，返回子数组的长度。

子数组越长，包含的元素越多，越可能不满足题目要求；反之，子数组越短，包含的元素越少，越可能满足题目要求。本题属于「越短越合法」，有这种性质的题目，可以用滑动窗口解决。

枚举子数组的右端点r i g h t rightright。同时用一个哈希表c n t cntcnt维护子数组内每个元素的出现次数。

如果f r u i t s [ r i g h t ] fruits[right]fruits[right]加入哈希表后，发现哈希表的大小超过了2 22，那么子数组不满足要求。移动子数组的左端点l e f t leftleft，把f r u i t s [ l e f t ] fruits[left]fruits[left]的出现次数减一，直到哈希表中的元素种数等于2 22。

⚠注意：如果f r u i t s [ l e f t ] fruits[left]fruits[left]的出现次数变成0 00，需要从c n t cntcnt中移除，表示子数组内少了一种元素。如果不移除，我们无法通过c n t cntcnt的大小判断窗口中的元素种数。

classSolution{publicinttotalFruit(int[]fruits){intans=0;intleft=0;Map<Integer,Integer>cnt=newHashMap<>();for(intright=0;right<fruits.length;right++){cnt.merge(fruits[right],1,Integer::sum);// fruits[right] 进入窗口while(cnt.size()>2){// 不满足要求intout=fruits[left];cnt.merge(out,-1,Integer::sum);// fruits[left] 离开窗口if(cnt.get(out)==0){cnt.remove(out);}left++;}ans=Math.max(ans,right-left+1);}returnans;}}

classSolution{public:inttotalFruit(vector<int>&fruits){intans=0,left=0;unordered_map<int,int>cnt;for(intright=0;right<fruits.size();right++){cnt[fruits[right]]++;// fruits[right] 进入窗口while(cnt.size()>2){// 不满足要求intout=fruits[left];cnt[out]--;// fruits[left] 离开窗口if(cnt[out]==0){cnt.erase(out);}left++;}ans=max(ans,right-left+1);}returnans;}};

classSolution:deftotalFruit(self,fruits:List[int])->int:ans=left=0cnt=defaultdict(int)forright,in_inenumerate(fruits):cnt[in_]+=1# fruits[right] 进入窗口whilelen(cnt)>2:# 不满足要求out=fruits[left]cnt[out]-=1# fruits[left] 离开窗口ifcnt[out]==0:delcnt[out]left+=1ans=max(ans,right-left+1)returnans

usestd::collections::HashMap;implSolution{pubfntotal_fruit(fruits:Vec<i32>)->i32{letmutans=0;letmutleft=0;letmutcnt=HashMap::new();for(right,&x)infruits.iter().enumerate(){*cnt.entry(x).or_insert(0)+=1;// fruits[right] 进入窗口whilecnt.len()>2{// 不满足要求letout=fruits[left];*cnt.entry(out).or_insert(0)-=1;// fruits[left] 离开窗口ifcnt[&out]==0{cnt.remove(&out);}left+=1;}ans=ans.max(right-left+1);}ansas_}}

functotalFruit(fruits[]int)(ansint){cnt:=map[int]int{}left:=0forright,in:=rangefruits{cnt[in]++// fruits[right] 进入窗口forlen(cnt)>2{// 不满足要求out:=fruits[left]cnt[out]--// fruits[left] 离开窗口ifcnt[out]==0{delete(cnt,out)}left++}ans=max(ans,right-left+1)}return}

vartotalFruit=function(fruits){letans=0,left=0;constcnt=newMap();for(letright=0;right<fruits.length;right++){cnt.set(fruits[right],(cnt.get(fruits[right])??0)+1);// fruits[right] 进入窗口while(cnt.size>2){// 不满足要求constout=fruits[left];cnt.set(out,cnt.get(out)-1);// fruits[left] 离开窗口if(cnt.get(out)===0){cnt.delete(out);}left++;}ans=Math.max(ans,right-left+1);}returnans;};