LeetCode - 904. 水果成篮

题目

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(vector<int>& fruits) {int left = 0;int right = 0;int ret = 0;unordered_map<int,int> sum;while(right < fruits.size()){sum[fruits[right]]++;while(sum.size() > 2){sum[fruits[left]]--;}ret = max(ret,right-left+1);right++;}return ret;}
};

代码主要问题在于：

当sum.size() > 2时，你只减少了sum[fruits[left]]--，但是没有移动left指针，

也没有在sum[fruits[left]]为0时将其从map中删除。这样会导致死循环或统计错误。

正确写法

class Solution {
public:int totalFruit(vector<int>& fruits) {int left = 0, right = 0, ret = 0;unordered_map<int, 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;}
};