LeetCode 题解工作台
分糖果
Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。 医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（ n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃…
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们用一个哈希表来存储糖果的种类，如果糖果的种类数小于 $n / 2$，那么 Alice 最多可以吃到的糖果种类数就是糖果的种类数；否则，Alice 最多可以吃到的糖果种类数就是 $n / 2$。 时间复杂度 ，空间复杂度 。其中 为糖果的数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。
医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。
给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。
示例 1：
输入：candyType = [1,1,2,2,3,3] 输出：3 解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。
示例 2：
输入：candyType = [1,1,2,3] 输出：2 解释：Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3]，她只能吃到两种不同类的糖。
示例 3：
输入：candyType = [6,6,6,6] 输出：1 解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。
提示：
n == candyType.length2 <= n <= 104n是一个偶数-105 <= candyType[i] <= 105
解题思路
方法一：哈希表
我们用一个哈希表来存储糖果的种类，如果糖果的种类数小于 ，那么 Alice 最多可以吃到的糖果种类数就是糖果的种类数；否则，Alice 最多可以吃到的糖果种类数就是 。
时间复杂度 ，空间复杂度 。其中 为糖果的数量。
class Solution:
def distributeCandies(self, candyType: List[int]) -> int:
return min(len(candyType) >> 1, len(set(candyType)))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should efficiently use hash lookup or set operations to track unique candy types.
- question_mark
Look for clarity in explaining the decision-making process between total unique types and n / 2 limit.
- question_mark
Verify that the candidate handles edge cases like arrays with one type of candy.
常见陷阱
外企场景- error
Failing to correctly identify the unique types by not using a hash set or similar structure.
- error
Not handling the case where the number of unique candy types is less than n / 2, which could lead to an incorrect result.
- error
Overcomplicating the solution by attempting unnecessary optimizations or algorithms.
进阶变体
外企场景- arrow_right_alt
What if Alice had to eat a fixed number of candies, regardless of type?
- arrow_right_alt
What if candyType had no duplicates, and Alice needed to eat as many different types as possible?
- arrow_right_alt
What if the problem constraints changed and n was no longer even?