LeetCode 575. 分糖果

2023-10-10 HGNULB 约 8 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 575. 分糖果

题意分析

给一个长度为偶数的数组 candyType，第 i 个元素表示第 i 颗糖的种类编号（编号本身可正可负，没有值域承诺）。医生要求 Alice 只能吃掉其中一半，也就是恰好 n / 2 颗。问在这个数量限制下，她最多能吃到多少不同种类的糖。

「数组长度保证是偶数」这个条件很关键，它让 n / 2 一定是整数，不需要考虑向上还是向下取整。「求不同种类数」直接指向去重，而糖果编号范围题面给到了 $-10^5$ 到 $10^5$，既不是从 $0$ 开始也不是紧凑排列，所以不能直接拿编号当数组下标（除非做偏移）。

真正要想清楚的是这道题里的选择自由度到底有多大。因为同种类的糖是完全等价的，而且每种糖至少存在一颗，Alice 挑选时可以完全按自己的意愿指定拿哪些——不存在「某两种糖必须一起拿」这类耦合。这意味着这不是一个背包或贪心问题，而是一个纯粹的计数取小问题。

边界上要覆盖：所有糖都是同一种（答案是 $1$，而不是 n / 2）；所有糖种类互不相同（答案是 n / 2，被数量卡住）；种类数恰好等于 n / 2（两个上界相等）；数组长度为 $2$ 的最小规模。数组长度上限是 $10^4$，量级极小，线性做法绰绰有余。

解法：去重计数

核心思路

先想暴力：枚举「吃哪 n / 2 颗」的所有组合，对每种组合数一下种类数取最大。组合数是 $\binom{n}{n/2}$，在 $n = 10^4$ 时是天文数字，完全不可行。瓶颈在于它把「选哪些」当成了需要搜索的决策，但实际上这些决策之间毫无冲突。

关键观察分两步。第一步，答案有两个天然上界：一是种类上界，Alice 吃到的不同种类数不可能超过糖果盒里总共存在的种类数 distinct；二是数量上界，她总共只能吃 n / 2 颗，而每多一个种类至少要占用一颗，所以不同种类数也不可能超过 n / 2。因此答案不超过 $\min(distinct, n/2)$。

第二步，这个上界一定能取到。若 distinct <= n / 2，就从每个种类里各拿一颗（共 distinct 颗，不超额），剩下的名额随便用重复的糖填满即可，种类数达到 distinct；若 distinct > n / 2，就从 distinct 个种类里任选 n / 2 个各拿一颗，恰好用完名额，种类数达到 n / 2。两种情况都构造出了达到上界的方案，所以上界即为答案。

于是本题的「状态定义」退化得极其简单：只需要 distinct 这一个量，即数组中互异元素的个数，答案就是 $\min(distinct, n/2)$。所有关于「先拿哪颗」的顺序、贪心、搜索全部被这条构造性论证消掉了。剩下的工程问题只有一个——怎么求互异元素个数，用哈希集合一趟遍历即可，这也是题目挂「哈希表」标签的原因。

解题步骤

建一个空的哈希集合（Java 用 HashSet<Integer>，Go 用 map[int]struct{}）。理由：糖果编号可能为负且分布稀疏，用数组做桶需要 $2 \times 10^5 + 1$ 的偏移数组，哈希集合对值域无假设，更通用也更好写。Go 里用 struct{} 而非 bool 作值类型，是因为空结构体不占内存。

一趟遍历 candyType，把每个元素塞进集合。理由：集合的 add 天然去重，不需要先判存在再插入，也不需要排序；用排序去重虽然也对，但会把复杂度抬到 $O(n \log n)$，且在面试里显得没抓到「哈希表」这个考点。

计算数量上界 limit = candyType.length / 2。理由：题目保证数组长度为偶数，所以整除不会丢精度；这里必须用数组长度而不是集合大小去除以 $2$，两者语义完全不同。

返回 Math.min(set.size(), limit)。理由：这一步同时封住了两个上界，前面的构造性论证保证了这个值可达，因此它既是上界也是答案。Go 里没有内置的整数 min，用一个 if 手写比较即可。

以 candyType = [1, 1, 2, 2, 3, 3] 走一遍：n = 6，limit = 3。遍历时集合依次变化为 {1}（第二个 1 重复插入无效）、{1, 2}、{1, 2, 3}，最终 distinct = 3。答案 $\min(3, 3) = 3$——Alice 吃 $3$ 颗，从每种各拿一颗，正好吃满三种。再用 candyType = [1, 1, 2, 3] 走一遍：n = 4，limit = 2，集合为 {1, 2, 3}，distinct = 3，答案 $\min(3, 2) = 2$——虽然有三个种类，但她只能吃两颗，最多尝到两种。最后用 candyType = [6, 6, 6, 6] 走一遍：limit = 2，集合为 {6}，distinct = 1，答案 $\min(1, 2) = 1$——名额还剩一个但没有新种类可吃，说明 min 里的另一边确实会生效，两个上界缺一不可。

代码实现

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();
        for (int t : candyType) {
            set.add(t);
        }

        return Math.min(set.size(), candyType.length / 2);
    }
}

func distributeCandies(candyType []int) int {
    set := make(map[int]struct{})
    for _, v := range candyType {
        set[v] = struct{}{}
    }

    limit := len(candyType) / 2
    if len(set) < limit {
        return len(set)
    }
    return limit
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是 candyType 的长度。只做一趟遍历，每次哈希插入的均摊代价是 $O(1)$；最后的 min 和取长度都是 $O(1)$。

空间复杂度：$O(n)$，哈希集合最坏情况下要存下所有互异元素，当数组中种类全不相同时集合大小就是 $n$。除集合外只用了一个整型变量，是常数额外空间。

关键点总结

遇到「在容量限制下最大化种类 / 覆盖数」这类问题，先检查各个选择之间是否互相独立。一旦独立，最优解通常就是几个显式上界取最小，根本不需要搜索或 DP，本题就是最干净的例子。

给出上界之后必须补一句可达性构造，否则 $\min$ 只是上界不是答案。面试里只说「答案是 min(distinct, n/2)」而不解释「为什么一定取得到」，会被追问；标准答法是分两种情况各给一个具体的取法。

值域稀疏或含负数时，哈希集合优于计数数组；值域紧凑且小时（比如只含小写字母）计数数组更快。要能说出这条选型依据，而不是无脑用 HashSet。

数量上界要用原数组长度除以 $2$，而不是去重之后的大小。这类「分母该取哪个量」的细节是简单题里最常见的失分点。

面试视角：字节和华为把这题当作暖场题，考的不是编码而是能否快速把一个看似有选择过程的问题识别成计数问题。理想的作答节奏是：三十秒内说出「答案是种类数和 n/2 的较小值」，再花一分钟补上两个方向的构造证明，最后写五行代码。如果面试官追问优化，可以提「若编号值域已知且紧凑，可以用长度为值域大小的布尔数组代替哈希集合，常数更小」。

易错点总结

错误写法：返回 set.size() 而忘记与 n / 2 取最小 → 用例 [1, 1, 2, 3] → 返回 $3$，但 Alice 只能吃 $2$ 颗，正确答案是 $2$。

错误写法：返回 candyType.length / 2 而忘记与种类数取最小 → 用例 [6, 6, 6, 6] → 返回 $2$，但盒子里只有一种糖，正确答案是 $1$。

错误写法：数量上界写成 set.size() / 2 → 用例 [1, 1, 2, 2, 3, 3] → set.size() = 3，上界算成 $1$，返回 $1$，正确答案是 $3$；分母必须是原数组长度。

错误写法：用计数数组 int[100001] 且直接用 candyType[i] 当下标 → 用例 [-1, -1, 2, 2] → 编号为负，下标为 $-1$，抛数组越界异常；正确做法是加上 $10^5$ 的偏移。

错误写法：先排序再用相邻比较去重，但比较条件写成 if (a[i] != a[i - 1]) distinct++ 却把 distinct 初始化为 $0$ 并从 i = 0 开始 → 用例 [1, 1, 2] → i = 0 时访问 a[-1] 越界；从 i = 1 起算又会漏掉第一个元素，distinct 少 $1$，[1, 1] 返回 $0$ 而正确答案是 $1$。

错误写法：Go 里用 map[int]bool 并在遍历后统计 len(set)，但插入时写成 set[v] = true 之后又在别处按 if set[v] 判断并 delete → 用例 [1, 1, 2] → 重复元素触发删除逻辑，len(set) 少算，返回值偏小。

错误写法：认为「同种类的糖不能重复吃」，于是在 distinct < n / 2 时返回 distinct 却在相等时返回 distinct - 1 → 用例 [1, 1, 2, 2] → distinct = 2，n / 2 = 2，返回 $1$，正确答案是 $2$；题目只限制总颗数，同种类可以重复吃。

错误写法：把 n / 2 写成 n >> 1 之后又在别处用 (n + 1) / 2 做向上取整 → 用例 [1, 2, 3, 4] → 两处不一致，上界算成 $2$ 和 $3$ 混用；题目保证 n 为偶数，全程用向下取整即可，混入向上取整会在推理中引入不存在的分支。

错误写法：用双重循环 $O(n^2)$ 判重统计种类数 → 用例长度 $10^4$ 且元素全不相同的数组 → 约 $5 \times 10^7$ 次比较，虽可能勉强通过但白白丢掉「哈希表」这个考点，面试中会被要求重写。

错误写法：Java 里把 candyType 装箱成 Integer[] 后用 contains 在 List 上判重 → 用例长度 $10^4$ 的数组 → List.contains 是 $O(n)$，总复杂度退化成 $O(n^2)$，同时 Integer 缓存范围之外的对象比较若误用 == 还会判重失败。

相似题目

题目	难度	考察点
217. 存在重复元素	简单	同样一趟哈希去重，但只需判断集合大小是否等于数组长度，无需取最小
349. 两个数组的交集	简单	去重之后还要做两个集合的求交，考察集合运算而非计数上界
1160. 拼写单词	简单	从「只数种类」升级为「按每种字符的可用次数做逐项 min」
347. 前 K 个高频元素	中等	不仅要去重还要统计频次并做 Top-K 选择，需配合堆或桶排序
135. 分发糖果	困难	名字相近但完全不同，是带相邻约束的两趟贪心，选择之间存在强耦合