流媒体 网站开发,灵台教育局网站师资队伍建设,电商平台排行榜,网站改版规则题目
904. 水果成篮 - 力扣#xff08;LeetCode#xff09;
思路
题目本质
你有一个整数数组#xff0c;每个元素代表一种水果。你只能用两个篮子#xff0c;每个篮子只能装一种水果。你要在数组中找一个最长的连续子数组#xff0c;这个子数组里最多只包含两种不同的…题目
904. 水果成篮 - 力扣LeetCode
思路
题目本质
你有一个整数数组每个元素代表一种水果。你只能用两个篮子每个篮子只能装一种水果。你要在数组中找一个最长的连续子数组这个子数组里最多只包含两种不同的数字水果种类。
解题思路滑动窗口法
滑动窗口
用两个指针left和right表示当前连续子数组的左右边界。right每次向右扩展left根据需要向右收缩。
统计水果种类
用一个哈希表如unordered_map记录当前窗口内每种水果的数量。
窗口合法性
如果窗口内水果种类不超过2种窗口合法更新最大长度。
如果超过2种移动left指针直到窗口内只剩下2种水果。
更新答案
每次窗口合法时更新最大长度。
过程
以 [1,2,1,2,3] 为例
初始窗口 [1]种类1种。
扩展到 [1,2]种类2种。
扩展到 [1,2,1]种类2种。
扩展到 [1,2,1,2]种类2种。
扩展到 [1,2,1,2,3]种类3种不合法。此时需要移动left直到只剩2种水果。
读者可能出现的错误写法
class Solution {
public:int totalFruit(vectorint fruits) {int left 0;int right 0;int ret 0;unordered_mapint,int sum;while(right fruits.size()){sum[fruits[right]];while(sum.size() 2){sum[fruits[left]]--;}ret max(ret,right-left1);right;}return ret;}
};
代码主要问题在于
当sum.size() 2时你只减少了sum[fruits[left]]--但是没有移动left指针
也没有在sum[fruits[left]]为0时将其从map中删除。这样会导致死循环或统计错误。
正确写法
class Solution {
public:int totalFruit(vectorint fruits) {int left 0, right 0, ret 0;unordered_mapint, int sum;while (right fruits.size()) {sum[fruits[right]];while (sum.size() 2) {sum[fruits[left]]--;if (sum[fruits[left]] 0) {sum.erase(fruits[left]);}left;}ret max(ret, right - left 1);right;}return ret;}
};
