題目描述:fruits[i] 表示第 i 棵樹的水果種類,你有兩個籃子,每個籃子只能放一種水果(不限數量)。從某棵樹開始連續採摘,遇到第三種水果就必須停止。求最多能採幾個水果。本題等價於:找出最多含 2 種不同元素的最長子陣列長度。
解題思路:這是 LeetCode 340(至多 k 個不同字元的最長子字串)在 k=2 時的特例,使用滑動視窗搭配雜湊表。維護左指針 left、右指針 right,以及計數表 basket 記錄視窗內每種水果的數量。右指針向右擴展時加入 fruits[right]。若視窗內水果種類超過 2(basket.size() > 2),從左側收縮:將 fruits[left] 的計數減一,若歸零則從 basket 中移除,左指針右移,直到種類數回到 2 以內。維持合法視窗後,以 right - left + 1 更新最大長度。
時間複雜度:O(n) — right 和 left 各最多移動 n 次,雜湊表操作均為 O(1) 平均,整體 O(n)。
空間複雜度:O(1) — basket 最多同時存放 3 種水果(收縮前的瞬間),實際上是 O(1) 有界空間(水果種類至多 3 個)。
1. Initialize left = 0, maxFruits = 0, basket = empty map.
2. For right from 0 to n-1:
a. Add fruits[right] to basket (increment count).
b. While basket.size() > 2:
- Decrement basket[fruits[left]].
- If basket[fruits[left]] == 0, remove fruits[left] from basket.
- Increment left.
c. Update maxFruits = max(maxFruits, right - left + 1).
3. Return maxFruits.方法一:滑動視窗 + 雜湊表(最優解) — 如本題解,時間 O(n)、空間 O(1)(因為最多存 2 種水果,空間有界)。此為處理「至多 k 種不同元素最長子陣列」問題的通用模板。
方法二:滑動視窗 + 固定大小陣列 — 若水果種類數有限(例如題目保證 0 ≤ fruits[i] < fruits.length ≤ 10⁵),可用大小為 n 的陣列取代雜湊表,以 O(1) 最壞時間完成所有操作。時間 O(n)、空間 O(n)。實務上雜湊表已夠快。
方法三:暴力枚舉 — 枚舉所有起點,從每個起點向右延伸直到第三種水果出現。時間 O(n²)、空間 O(1)。思路直觀但大輸入超時。