LeetCode 题解工作台
水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果： 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用哈希表 维护当前窗口内的水果种类以及对应的数量，用双指针 和 维护窗口的左右边界。 遍历数组 ，将当前水果 加入窗口，即 ，然后判断当前窗口内的水果种类是否超过了 种，如果超过了 种，就需要将窗口的左边界 右移，直到窗口内的水果种类不超过 种为止。然后更新答案，即 $\textit{ans} = \max(\textit{ans}, i - j + 1)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
示例 1：
输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [1,2,3,2,2] 输出：4 解释：可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：可以采摘 [1,2,1,1,2] 这五棵树。
提示：
1 <= fruits.length <= 1050 <= fruits[i] < fruits.length
解题思路
方法一：哈希表 + 滑动窗口
我们用哈希表 维护当前窗口内的水果种类以及对应的数量，用双指针 和 维护窗口的左右边界。
遍历数组 ，将当前水果 加入窗口，即 ，然后判断当前窗口内的水果种类是否超过了 种，如果超过了 种，就需要将窗口的左边界 右移，直到窗口内的水果种类不超过 种为止。然后更新答案，即 。
遍历结束后，即可得到最终的答案。
1 2 3 2 2 1 4
^ ^
j i
1 2 3 2 2 1 4
^ ^
j i
1 2 3 2 2 1 4
^ ^
j i
时间复杂度 ，其中 为数组 的长度。空间复杂度 ，因为哈希表 中的键值对数量最多为 。
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
cnt = Counter()
ans = j = 0
for i, x in enumerate(fruits):
cnt[x] += 1
while len(cnt) > 2:
y = fruits[j]
cnt[y] -= 1
if cnt[y] == 0:
cnt.pop(y)
j += 1
ans = max(ans, i - j + 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Evaluate the candidate's understanding of sliding window techniques and hash tables.
- question_mark
Check if the candidate can optimize the window size and manage hash table updates efficiently.
- question_mark
Assess how the candidate handles edge cases, such as arrays with fewer than two distinct fruit types.
常见陷阱
外企场景- error
Failing to correctly manage the sliding window, leading to unnecessary re-scanning of parts of the array.
- error
Using a brute force approach that checks all subarrays instead of leveraging the sliding window and hash table.
- error
Overcomplicating the problem by not recognizing that the maximum valid subarray is the one with the largest window containing two distinct fruits.
进阶变体
外企场景- arrow_right_alt
Extend the problem to handle more than two fruit types.
- arrow_right_alt
Find the maximum number of fruits that can be picked from any subarray that contains exactly two distinct fruit types.
- arrow_right_alt
Optimize the solution for cases where the number of fruit types is dynamically provided as an input.