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

本文属于「征服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^50 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){intans0;intleft0;MapInteger,IntegercntnewHashMap();for(intright0;rightfruits.length;right){cnt.merge(fruits[right],1,Integer::sum);// fruits[right] 进入窗口while(cnt.size()2){// 不满足要求intoutfruits[left];cnt.merge(out,-1,Integer::sum);// fruits[left] 离开窗口if(cnt.get(out)0){cnt.remove(out);}left;}ansMath.max(ans,right-left1);}returnans;}}classSolution{public:inttotalFruit(vectorintfruits){intans0,left0;unordered_mapint,intcnt;for(intright0;rightfruits.size();right){cnt[fruits[right]];// fruits[right] 进入窗口while(cnt.size()2){// 不满足要求intoutfruits[left];cnt[out]--;// fruits[left] 离开窗口if(cnt[out]0){cnt.erase(out);}left;}ansmax(ans,right-left1);}returnans;}};classSolution:deftotalFruit(self,fruits:List[int])-int:ansleft0cntdefaultdict(int)forright,in_inenumerate(fruits):cnt[in_]1# fruits[right] 进入窗口whilelen(cnt)2:# 不满足要求outfruits[left]cnt[out]-1# fruits[left] 离开窗口ifcnt[out]0:delcnt[out]left1ansmax(ans,right-left1)returnansusestd::collections::HashMap;implSolution{pubfntotal_fruit(fruits:Veci32)-i32{letmutans0;letmutleft0;letmutcntHashMap::new();for(right,x)infruits.iter().enumerate(){*cnt.entry(x).or_insert(0)1;// fruits[right] 进入窗口whilecnt.len()2{// 不满足要求letoutfruits[left];*cnt.entry(out).or_insert(0)-1;// fruits[left] 离开窗口ifcnt[out]0{cnt.remove(out);}left1;}ansans.max(right-left1);}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}ansmax(ans,right-left1)}return}vartotalFruitfunction(fruits){letans0,left0;constcntnewMap();for(letright0;rightfruits.length;right){cnt.set(fruits[right],(cnt.get(fruits[right])??0)1);// fruits[right] 进入窗口while(cnt.size2){// 不满足要求constoutfruits[left];cnt.set(out,cnt.get(out)-1);// fruits[left] 离开窗口if(cnt.get(out)0){cnt.delete(out);}left;}ansMath.max(ans,right-left1);}returnans;};复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是f r u i t s fruitsfruits的长度。空间复杂度O ( 1 ) O(1)O(1)在任意时刻哈希表中至多有3 33个键值对3 33种不同元素。专题训练滑动窗口题单中的「2.1 越短越合法/求最长/最大」。