LeetCode-Go 题解精讲575. Distribute Candies哈希计数求分糖最大种类数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章以 LeetCode-Go 仓库中 575. Distribute Candies 题解目录 为核心完整拆解 LeetCode 第 575 题「分糖果」的题意、输入约束与最优解法。文章不仅还原原题解析还结合仓库内的 Go 源码实现与单元测试逐行讲解map去重计数 上限截断的解题范式并给出可直接复制运行的测试命令。读完本文你将掌握这一类统计种类数并施加分配上限问题的通用分析套路以及如何在该仓库中复现、验证该解法。题目描述给定一个长度为偶数的整数数组其中不同的数字代表不同种类的糖果每一个数字代表一颗对应种类的糖果。需要把这些糖果等量分给弟弟和妹妹返回妹妹最多可以获得多少种糖果。英文原文如下出自 575. Distribute Candies READMEGiven an integer array withevenlength, where different numbers in this array represent differentkindsof candies. Each number means one candy of the corresponding kind. You need to distribute these candiesequallyin number to brother and sister. Return the maximum number ofkindsof candies the sister could gain.示例 1Input: candies [1,1,2,2,3,3] Output: 3 Explanation: There are three different kinds of candies (1, 2 and 3), and two candies for each kind. Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. The sister has three different kinds of candies.数组中共有 3 种糖果每种 2 颗。妹妹与弟弟各分到 3 颗且妹妹拿到的 3 颗恰好互不相同[1,2,3]因此她获得了全部 3 个种类。示例 2Input: candies [1,1,2,3] Output: 2 Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1]. The sister has two different kinds of candies, the brother has only one kind of candies.数组中共有 3 种糖果1、2、3但每人只能分到4/2 2颗。妹妹最多只能拥有 2 种[2,3]而非全部 3 种——因为 2 颗的容量限制了她能收集的种类数上限。输入约束与边界条件原题在 README 的 Note 一节 中明确给出了两条约束数组长度范围[2, 10,000]且必然为偶数数组中元素的取值范围[-100,000, 100,000]。由此可以提炼出几个关键边界事实长度至少为 2因此每人至少分到 1 颗糖果结果最小为 1元素允许为负数去重统计时不能依赖数组下标或桶排序必须使用哈希结构这正是仓库解法选择map的直接原因由于长度必为偶数n/2一定是整数不存在每人 2.5 颗之类的取整问题。解题思路核心思路在原题 README 的 解题思路一节 中已经给出可归纳为两步统计种类数用map遍历数组去重得到糖果种类的总数len(map)施加上限截断妹妹最多只能拿到n/2颗糖果因此她能获得的最大种类数不可能超过n/2。最终答案取min(len(map), n/2)如果种类总数比n/2小返回len(map)种类少妹妹每种都能拿一颗否则返回n/2种类充足但妹妹的糖果数量上限是n/2最多只能集齐这么多种。为什么这个答案是最大的因为存在一个总是可达的构造只要种类数足够就能从每种糖果中各取一颗凑出n/2颗互不相同的糖果给妹妹剩余的糖果含重复的全部给弟弟。反过来无论怎么分配妹妹手上最多只有n/2颗种类数不可能超过糖果数所以n/2是一个严格的上界。两者结合即为最优值。与最大频次类问题的辨析本题属于统计种类distinct count 数量上限模型与「统计出现频次最高元素」如 Majority Element不同这里不需要记录每种糖果出现的具体次数只要知道这种糖是否存在因此map的值类型可以用零开销的空结构体struct{}而不是int。这一细节也体现在仓库源码中。源码实现解析仓库中的实际解法位于 575. Distribute Candies.go文件名与 LeetCode 题号保持一致遵循本仓库题号.题目名.go的命名规范package leetcode func distributeCandies(candies []int) int { n, m : len(candies), make(map[int]struct{}, len(candies)) for _, candy : range candies { m[candy] struct{}{} } res : len(m) if n/2 res { return n / 2 } return res }逐行解读n, m : len(candies), make(map[int]struct{}, len(candies))同时取出数组长度n并以len(candies)作为map的初始容量做预分配。由于种类数最多不超过数组长度这个容量上界是精确的可以避免扩容带来的哈希重建开销m[candy] struct{}{}对每个糖果种类去重。这里的关键技巧是使用空结构体struct{}作为 value。struct{}不占用任何内存与使用bool或int相比是纯零成本的存在标记res : len(m)len(m)即糖果的种类总数if n/2 res { return n / 2 }当种类数超过n/2时妹妹受限于糖果数量最多只能拿到n/2种return res否则返回全部种类数。代码风格上该实现严格遵守本仓库 README 中声明的 Google Golang Style Guide函数名使用小写驼峰包内私有函数由测试直接调用逻辑分支平铺直叙、无冗余 else。复杂度分析时间复杂度O(n)只需一次遍历完成哈希插入map平均插入/查询为O(1)空间复杂度O(n)map最多存储n个不同种类。在n ≤ 10,000的约束下该方案的时间与空间代价均在线性范围内是最优的可行解任何解法至少要读取全部输入因此Ω(n)是下界。测试与验证仓库为本题配套了完整单元测试位于 575. Distribute Candies_test.go采用本仓库统一的问题结构体 表格驱动测试风格type question575 struct { para575 ans575 } // para 是参数 // one 代表第一个参数 type para575 struct { one []int } // ans 是答案 // one 代表第一个答案 type ans575 struct { one int } func Test_Problem575(t *testing.T) { qs : []question575{ { para575{[]int{1, 1, 2, 2, 3, 3}}, ans575{3}, }, { para575{[]int{1, 1, 2, 3}}, ans575{2}, }, } ... }测试用例与题目的两个官方示例一一对应[1,1,2,2,3,3] → 3、[1,1,2,3] → 2。其中para575/ans575的结构命名体现了仓库的通用约定每个题目的测试文件都定义para输入参数与ans期望答案两类结构体并组合成question切片批量断言便于日后追加更多用例。在仓库根目录下可以通过以下方式单独运行本题测试go test -v ./leetcode/0575.Distribute-Candies/若要按仓库 CI 的方式生成全量覆盖率报告可执行根目录的 gotest.shbash gotest.sh该脚本会以atomic覆盖率模式一次性对./leetcode/...下全部题解执行测试并输出 coverage.txt。仓库以100% test coverage为目标本题两个官方示例用例即可完整覆盖distributeCandies的两条返回分支n/2截断分支与全量种类分支。扩展思考把解法抽象成通用范式本题看似简单但其去重计数 上限截断的骨架可以抽象为一个可复用的思维范式maxKinds min(种类数, 可容纳数量上限)这类题目在 LeetCode 中并不少见典型变体包括分给多人的变体若糖果需要分给k个人而非 2 人则每人糖果数量上限变为n/k答案变为min(len(map), n/k)思路完全一致最多 x 种的背包式问题当种类本身附带权重如每种种类的获取有额外约束时单纯的min不再成立需要退化为排序贪心或动态规划流式数据场景当数组无法一次性载入内存如数据来自流可以借助哈希集合维护已见过种类集合在流式扫描中实时维护len(map)并随时做截断判断仍保持O(1)均摊空间增量。本题的 Go 实现还演示了两个值得在实际工程中复用的语言级技巧用make(map[int]struct{}, len)做精确容量预分配以及用空结构体struct{}作为仅需存在性语义的集合元素。前者在已知上界的大数组场景下能显著减少扩容次数后者让集合语义在 Go 中不再需要额外引入第三方依赖。小结题意偶数长度数组等分给两人求妹妹最多能拿到的糖果种类数解法map去重统计种类数k答案即min(k, n/2)时间复杂度O(n)、空间复杂度O(n)仓库佐证完整实现见 575. Distribute Candies.go官方两个示例均被 575. Distribute Candies_test.go 覆盖可在本地通过go test -v ./leetcode/0575.Distribute-Candies/一键复现。掌握这道题的核心不在于记住返回 min(种类数, n/2)这个结论而在于理解为什么种类数需要与数量上限取最小值——这是所有分配上限 种类/多样性最大化类问题的共同数学内核。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考