904. 水果成篮
题目描述
一排果树从左到右排列，输入整数数组 fruits，fruits[i] 是第 i 棵树结的水果种类。
你有两个篮子，每个篮子只能装一种水果，但数量不限。你可以从任意一棵树开始，向右逐棵采摘，每棵树恰好摘一个水果，且必须放进某个篮子。一旦遇到的水果种类两个篮子都放不进，就必须停下。
返回最多能摘到多少个水果。换句话说，就是求最多只含两种不同值的连续子数组的最大长度。
示例 1
输入：fruits = [1,2,1] 输出：3
解释：只有两种水果，三棵树全部可摘。
示例 2
输入：fruits = [0,1,2,2] 输出：3
解释：从下标 1 开始摘 [1,2,2]。
示例 3
输入：fruits = [1,2,3,2,2] 输出：4
解释：从下标 1 开始摘 [2,3,2,2]。
数据范围
1 <= fruits.length <= 10^50 <= fruits[i] < fruits.length
解题思路
问题等价于：求最多包含 2 种不同数字的最长连续子数组。用哈希表 cnt 记录窗口内各种类数量。right 每步右移并加入；种类超过 2 时，left 右移并减少对应计数，计数归 0 就删除该键，直到种类回到 2。每步用窗口长度更新答案。
为什么正确
每次更新 ans 时，窗口 fruits[left..right] 是以 right 结尾、至多 2 种水果的最长窗口；len(cnt) 就是窗口内的种类数。
复杂度分析
时间 O(n)，每个下标最多进出窗口各一次；空间 O(1)，哈希表最多 3 个键。
易错点
计数减到 0 时一定要把键从哈希表中删除，否则 len(cnt) 不会减少，while 会把窗口收缩到空。收缩要用 while，不能只移一格。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
cnt = collections.Counter()
left = ans = 0
for right, x in enumerate(fruits):
cnt[x] += 1
while len(cnt) > 2:
y = fruits[left]
cnt[y] -= 1
if cnt[y] == 0:
del cnt[y]
left += 1
ans = max(ans, right - left + 1)
return ansclass Solution {
public int totalFruit(int[] fruits) {
Map<Integer, Integer> cnt = new HashMap<>();
int left = 0, ans = 0;
for (int right = 0; right < fruits.length; right++) {
cnt.merge(fruits[right], 1, Integer::sum);
while (cnt.size() > 2) {
int y = fruits[left];
cnt.merge(y, -1, Integer::sum);
if (cnt.get(y) == 0) {
cnt.remove(y);
}
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> cnt;
int left = 0, ans = 0;
for (int right = 0; right < (int)fruits.size(); right++) {
cnt[fruits[right]]++;
while (cnt.size() > 2) {
int y = fruits[left];
cnt[y]--;
if (cnt[y] == 0) {
cnt.erase(y);
}
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};func totalFruit(fruits []int) int {
cnt := map[int]int{}
left, ans := 0, 0
for right, x := range fruits {
cnt[x]++
for len(cnt) > 2 {
y := fruits[left]
cnt[y]--
if cnt[y] == 0 {
delete(cnt, y)
}
left++
}
ans = max(ans, right-left+1)
}
return ans
}var totalFruit = function(fruits) {
const cnt = new Map();
let left = 0, ans = 0;
for (let right = 0; right < fruits.length; right++) {
cnt.set(fruits[right], (cnt.get(fruits[right]) || 0) + 1);
while (cnt.size > 2) {
const y = fruits[left];
cnt.set(y, cnt.get(y) - 1);
if (cnt.get(y) === 0) {
cnt.delete(y);
}
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
};function totalFruit(fruits: number[]): number {
const cnt = new Map<number, number>();
let left = 0, ans = 0;
for (let right = 0; right < fruits.length; right++) {
cnt.set(fruits[right], (cnt.get(fruits[right]) || 0) + 1);
while (cnt.size > 2) {
const y = fruits[left];
cnt.set(y, cnt.get(y)! - 1);
if (cnt.get(y) === 0) {
cnt.delete(y);
}
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}