給定整數陣列
fruits（代表一排果樹的水果種類），你有兩個籃子，每個籃子只能放一種水果。從任一棵樹開始連續採集，遇到第三種水果就停止。回傳最多能採集的水果數量。
Example:
Input: fruits = [1,2,1,2,3] Output: 4（子陣列 [1,2,1,2] 只有兩種水果）
Intuition
TIP
核心思路：本質是「最長的最多包含 2 種不同元素的連續子陣列」，用滑動視窗 + HashMap 維護種類計數。
- 兩個籃子 = 最多兩種不同水果
- 經典的「最多 k 種不同元素的最長子陣列」模板，這裡 k = 2
- HashMap 記錄視窗內每種水果的數量，超過 2 種時收縮左邊界
Approaches
1. Brute Force — O(n²) / O(1)
- Idea: 嘗試每個起點，向右延伸直到超過 2 種水果
- Time:
O(n²) - Space:
O(1)- 最多追蹤 3 種
Brute Force Code
class Solution {
fun totalFruit(fruits: IntArray): Int {
var result = 0
for (i in fruits.indices) {
val types = mutableSetOf<Int>()
var j = i
while (j < fruits.size) {
types.add(fruits[j])
if (types.size > 2) break
j++
}
result = maxOf(result, j - i)
}
return result
}
}⭐ 2. Sliding Window + HashMap — O(n) / O(1)
- Idea: 右指針擴展視窗，用 HashMap 記錄各水果數量；當種類 > 2 時，收縮左邊界直到種類 <= 2
- Time:
O(n)- 左右指針各遍歷一次 - Space:
O(1)- HashMap 最多 3 個 entry
class Solution {
fun totalFruit(fruits: IntArray): Int {
val count = mutableMapOf<Int, Int>()
var left = 0
var result = 0
for (right in fruits.indices) {
count[fruits[right]] = (count[fruits[right]] ?: 0) + 1
while (count.size > 2) {
val leftFruit = fruits[left]
count[leftFruit] = count[leftFruit]!! - 1
if (count[leftFruit] == 0) count.remove(leftFruit)
left++
}
result = maxOf(result, right - left + 1)
}
return result
}
}WARNING
HashMap 中計數歸零時要立即 remove，否則 count.size 不會正確反映種類數。
🔑 Takeaways
- Pattern: 可變大小滑動視窗 + HashMap 計數（At Most K Distinct 模板）
- Key trick: 此題是「最多 k 種不同元素的最長子陣列」的特例（k=2），同樣的模板可解 LC 340 (k 種) 等變體