淘宝推广网站怎么做,手机价格,深圳龙岗个人网站建设,免费的自助设计网站题目解析
904. 水果成篮 算法讲解
这道题的本质就是#xff1a;寻找一段连续的区域#xff08;子数组#xff09;#xff0c;这一段连续的区域里面最多包含两种水果#xff0c;因为有可能这一段连续的区域里面全是一种水果#xff0c;比如#xff1a;f(x) {1,1,1,1,…题目解析
904. 水果成篮 算法讲解
这道题的本质就是寻找一段连续的区域子数组这一段连续的区域里面最多包含两种水果因为有可能这一段连续的区域里面全是一种水果比如f(x) {1,1,1,1,1,1,1} 我们这道题需要使用一个数据结构Hash使用Hash是为了更方便 快捷的寻找出这一种水果的数量 但我们cont大于两种水果的时候说明我们已经找到了这一段连续的区间只不过需要继续往后面走看看有没有更合适的所以就需要继续移动窗口
class Solution {
public:int totalFruit(vectorint nums) {//寻找子数组子数组中包含不超过两个种类的水果 有可能全部都是same数int left 0, right 0;//数组的长度最大到10^5int Hash[100000] {0};int n nums.size();int count 0; //记录种类个数int ret 0;while(right n){if(Hash[nums[right]] 0)count;Hash[nums[right]];//走到这里说明已经遇到了第三种水果while(count 2){Hash[nums[left]]--; if(Hash[nums[left]] 0)count--;left;}ret max(ret, right - left 1);right;} return ret;}
};
