題目

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;}
};