Leetcode 2994 Distribute Candies Among Children II从三重循环暴力到 O(1) 容斥原理的多语言实战指南【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇指南围绕仓库文档 articles/distribute-candies-among-children-ii.md 讲解 Leetcode 2994「Distribute Candies Among Children II」的完整解法演进从 $O(l^3)$ 的暴力枚举到两重循环剪枝、单重循环区间计数最终收敛到基于容斥原理Inclusion-Exclusion的 $O(1)$ 解法。读完本篇你将掌握「固定一个变量、将剩余变量转化为区间计数」这一通用优化手法以及用隔板法 容斥原理对受限整数划分问题做常时间求值的完整推导并能直接复用文档中覆盖 9 种语言的实现代码。问题定义与前置知识题目将n颗相同的糖分给三个孩子 A、B、C每个孩子最多得到limit颗即每个孩子的分配量在[0, limit]区间内求恰好分完n颗的分配方案总数。答案可能很大各语言实现均以 64 位整数long/long long/int64/Long返回。原文档在Prerequisites一节列出了三个前置知识点下面结合本问题的具体用法逐一说明组合学基础Combinatorics Basics不带上限约束时求非负整数方程a b c n的解的个数属于经典「隔板法」Stars and Bars问题——n个球与 2 块隔板排成一排共有C(n2, 2) (n2)(n1)/2种摆法。这个闭式表达式是整个解法体系的基石。枚举技巧Enumeration Techniques系统地遍历所有合法取值组合并用min(n, limit)这类上界收紧循环范围、用「确定一个变量后其余变量取值落在区间内」代替内层循环。容斥原理Inclusion-Exclusion Principle通过「加/减重叠集合」消除重复计数把「每个变量都不超过 limit」的上限约束从枚举中剥离转化为对「违反约束的个数」的交替加减。需要说明本文所有代码示例均继承自仓库文档 articles/distribute-candies-among-children-ii.md该文档以 Tab 形式提供了 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 共 9 种语言的完整实现下文为篇幅考虑每种解法节选代表性语言其余语言的实现以原文档为准。解法一暴力枚举时间复杂度 O(l³)直觉最直接的思路是对三个孩子的分配量做全组合让a、b、c各自从0枚举到limit仅当a b c n时计数加一。思路简单直观但当limit达到题面允许的 $10^9$ 量级时循环次数为 $O(l^3)$必然超时——它的价值在于提供一个可以离线验证其他解法正确性的基准。算法步骤初始化计数器res 0三重嵌套循环遍历每个孩子可能的糖果数0到limit含limit本身对每组(a, b, c)检查a b c n成立则res 1返回res。多语言实现class Solution: def distributeCandies(self, n: int, limit: int) - int: res 0 for a in range(limit 1): for b in range(limit 1): for c in range(limit 1): if a b c n: res 1 return respublic class Solution { public long distributeCandies(int n, int limit) { long res 0; for (int a 0; a limit; a) { for (int b 0; b limit; b) { for (int c 0; c limit; c) { if (a b c n) { res; } } } } return res; } }class Solution { public: long long distributeCandies(int n, int limit) { long long res 0; for (int a 0; a limit; a) { for (int b 0; b limit; b) { for (int c 0; c limit; c) { if (a b c n) { res; } } } } return res; } };func distributeCandies(n int, limit int) int64 { var res int64 0 for a : 0; a limit; a { for b : 0; b limit; b { for c : 0; c limit; c { if abc n { res } } } } return res }复杂度时间 $O(l^3)$空间 $O(1)$$l$ 即给定的limit。原文档在Time Space Complexity一节给出的结论与此一致。解法二两重循环剪枝时间复杂度 O(min(n, limit)²)直觉暴力的浪费在于当a b已确定时c的值被唯一确定为c n - a - b因此第三层循环完全不需要存在只需检查这个确定值是否落在[0, limit]内。更进一步a不必遍历到limit分配量超过n本身没有意义c会变成负数所以外层上界收紧为min(n, limit)内层上界为min(n - a, limit)。算法步骤初始化res 0a从0循环到min(n, limit)对每个ab从0循环到min(n - a, limit)令c n - a - b若c limit此时c 0由内层上界保证计数器加一返回res。多语言实现class Solution: def distributeCandies(self, n: int, limit: int) - int: res 0 for a in range(min(n, limit) 1): for b in range(min(n - a, limit) 1): if n - a - b limit: res 1 return respublic class Solution { public long distributeCandies(int n, int limit) { long res 0; int maxA Math.min(n, limit); for (int a 0; a maxA; a) { int maxB Math.min(n - a, limit); for (int b 0; b maxB; b) { if (n - a - b limit) { res; } } } return res; } }class Solution { public: long long distributeCandies(int n, int limit) { long long res 0; int maxA min(n, limit); for (int a 0; a maxA; a) { int maxB min(n - a, limit); for (int b 0; b maxB; b) { if (n - a - b limit) { res; } } } return res; } };func distributeCandies(n int, limit int) int64 { var res int64 0 maxA : min(n, limit) for a : 0; a maxA; a { maxB : min(n-a, limit) for b : 0; b maxB; b { if n-a-b limit { res } } } return res }复杂度时间 $O(\min(n, limit)^2)$空间 $O(1)$。注意 Go 示例中min依赖语言标准库提供的内建函数Go 1.21这是原文档示例的运行前提。解法三单重枚举 区间计数Enumeration I时间复杂度 O(min(n, limit))直觉解法二剩下的内层循环其实仍在逐个检查b但合法的b恰好构成一个连续区间可以直接数出个数上界b_max min(n - a, limit)既要保证b ≤ limit又要保证c n - a - b ≥ 0即b ≤ n - a下界b_min max(0, n - a - limit)其中n - a - limit这一项正是保证c ≤ limit的关键——若b太小剩余糖果会被迫全压给 C 而超限。两个约束取交集后合法方案数就是b_max - b_min 1当b_max b_min时内层循环被彻底消掉。算法步骤初始化res 0a从0循环到min(n, limit)对每个a计算b_max min(n - a, limit)与b_min max(0, n - a - limit)若b_max b_min把(b_max - b_min 1)累加进计数器返回res。多语言实现class Solution: def distributeCandies(self, n: int, limit: int) - int: res 0 for a in range(min(n, limit) 1): b_max min(n - a, limit) b_min max(0, n - a - limit) if b_max b_min: res b_max - b_min 1 return respublic class Solution { public long distributeCandies(int n, int limit) { long res 0; for (int a 0, aMax Math.min(n, limit); a aMax; a) { int bMax Math.min(n - a, limit); int bMin Math.max(0, n - a - limit); if (bMax bMin) { res (long)(bMax - bMin 1); } } return res; } }class Solution { public: long long distributeCandies(int n, int limit) { long long res 0; int aMax min(n, limit); for (int a 0; a aMax; a) { int bMax min(n - a, limit); int bMin max(0, n - a - limit); if (bMax bMin) { res (long long)(bMax - bMin 1); } } return res; } };func distributeCandies(n int, limit int) int64 { var res int64 0 aMax : min(n, limit) for a : 0; a aMax; a { bMax : min(n-a, limit) bMin : max(0, n-a-limit) if bMax bMin { res int64(bMax - bMin 1) } } return res }复杂度时间 $O(\min(n, limit))$空间 $O(1)$。注意 Java/C/C#/Kotlin 示例中都对累加量做了显式的整型提升如(long)(bMax - bMin 1)因为方案总数可超过 32 位整数范围——这是多语言实现中容易忽略的溢出点。解法四提前剪枝的等价写法Enumeration II直觉这是解法三的微调版本令rem n - a表示分给 A 之后剩余要给 B、C 的糖果数。若rem 2 * limit则 B、C 每人至多limit颗两人合起来最多2 * limit颗无解该a值可以直接跳过。通过这一提前判断解法三的b_max b_min分支检查被显式化语义更清晰两种写法时间复杂度相同但剪枝条件在极端输入下能少做无用计算。算法步骤初始化res 0a从0循环到min(n, limit)令rem n - a若rem 2 * limit则跳过本次迭代否则合法(b, c)配对数为min(rem, limit) - max(0, rem - limit) 1累加进res返回res。多语言实现class Solution: def distributeCandies(self, n: int, limit: int) - int: res 0 for a in range(min(n, limit) 1): if n - a 2 * limit: res min(n - a, limit) - max(0, n - a - limit) 1 return respublic class Solution { public long distributeCandies(int n, int limit) { long res 0; int maxA Math.min(n, limit); for (int a 0; a maxA; a) { int rem n - a; if (rem 2L * limit) { int hi Math.min(rem, limit); int lo Math.max(0, rem - limit); res (hi - lo 1); } } return res; } }func distributeCandies(n int, limit int) int64 { var res int64 0 maxA : min(n, limit) for a : 0; a maxA; a { rem : n - a if rem 2*limit { hi : min(rem, limit) lo : max(0, rem-limit) res int64(hi - lo 1) } } return res }复杂度时间 $O(\min(n, limit))$空间 $O(1)$。Java 示例中2L * limit的写法同样是为避免2 * limit在int范围内溢出。解法五容斥原理时间复杂度 O(1)直觉与推导把约束问题转化为「总数 − 违规数」。设 $m$ 为非负剩余糖果数则方程a b c m的非负整数解个数为隔板法闭式解$$\text{ways}(m) \binom{m2}{2} \frac{(m2)(m1)}{2}$$不加约束时j 0总方案数为 $\text{ways}(n)$。接下来逐层处理「某个孩子超过limit」即拿到 $\geq limit 1$ 颗的违规情形1 个孩子超限任选一个孩子3 种选法先给他塞limit 1颗剩余 $n - (limit1)$ 颗仍按隔板法分配违规数 $3 \cdot \text{ways}(n - (limit1))$需要减去2 个孩子超限在上一轮被减了两次容斥要求加回$3 \cdot \text{ways}(n - 2(limit1))$从 3 个孩子里选 2 个3 个孩子超限再加一次也要减减去$\text{ways}(n - 3(limit1))$。合并起来就是统一的求和式$$\text{ans} \sum_{j0}^{3} (-1)^{j} \binom{3}{j} \cdot \text{ways}!\big(n - j \cdot (limit 1)\big)$$其中 $\binom{3}{j} \in {1, 3, 3, 1}$ 对应文档中的数组C3 [1, 3, 3, 1]当 $n - j(limit1) 0$ 时该项无意义直接跳过continue。求和只有 4 项故时间复杂度 $O(1)$。数值验证可用此例自测实现n 5, limit 2时暴力枚举可手验解仅为(2,2,1)的 3 种排列答案为 3代入容斥公式j0项 $\binom{7}{2} 21$j1项 $-3 \times \binom{4}{2} -18$j2,3项因 $m 0$ 跳过合计 $21 - 18 3$与暴力结果一致。算法步骤对应原文档 Algorithm定义二项系数从m2中选 2即(m2)*(m1)/2j从0到3计算m n - j * (limit 1)若m 0跳过该项计算ways (m2)*(m1)/2按容斥规律取交替符号j为偶数取 奇数取 −并乘以C3[j]累加所有项返回结果。多语言实现class Solution: def distributeCandies(self, n: int, limit: int) - int: C3 [1, 3, 3, 1] res 0 for j in range(4): m n - j * (limit 1) if m 0: continue ways (m 2) * (m 1) // 2 sign -1 if j % 2 else 1 res sign * C3[j] * ways return respublic class Solution { public long distributeCandies(int n, int limit) { int[] C3 {1, 3, 3, 1}; long res 0; for (int j 0; j 4; j) { long m n - j * (limit 1); if (m 0) continue; long ways (m 2) * (m 1) / 2; int sign (j % 2 0) ? 1 : -1; res sign * C3[j] * ways; } return res; } }class Solution { public: long long distributeCandies(int n, int limit) { int C3[4] {1, 3, 3, 1}; long long res 0; for (int j 0; j 4; j) { long long m n - j * (limit 1); if (m 0) continue; long long ways (m 2) * (m 1) / 2; int sign (j % 2 0 ? 1 : -1); res sign * C3[j] * ways; } return res; } };impl Solution { pub fn distribute_candies(n: i32, limit: i32) - i64 { let c3: [i64; 4] [1, 3, 3, 1]; let mut res: i64 0; for j in 0..4 { let m n as i64 - j as i64 * (limit as i64 1); if m 0 { continue; } let ways (m 2) * (m 1) / 2; let sign: i64 if j % 2 0 { 1 } else { -1 }; res sign * c3[j] * ways; } res } }复杂度时间 $O(1)$空间 $O(1)$。实现细节上各语言示例如 Java 的long m、Rust 的as i64、Kotlin 的n.toLong()都把中间量提升到 64 位防止limit接近 $10^9$ 时(m2)*(m1)乘积溢出 32 位整型。常见陷阱Common Pitfalls原文档Common Pitfalls一节总结了三个高频错误值得逐条对照检查。陷阱一遗漏孩子 C 的下界约束在解法二/三的计算中合法b区间由上下界共同决定。只检查上界c 0而不检查c limit会多计# Wrong: Only checking upper bound for b in range(min(n - a, limit) 1): c n - a - b if c 0: # Missing: c limit check! res 1 # Correct: Check both bounds b_max min(n - a, limit) b_min max(0, n - a - limit) # Ensures c limit if b_max b_min: res b_max - b_min 1b_min max(0, n - a - limit)中的第二项正是把c ≤ limit反解到b上的结果。陷阱二循环边界的 Off-by-One0与limit都是合法分配量。写成range(limit)或等价形式会漏掉「某孩子恰好拿limit颗」的方案# Wrong: Missing limit value for a in range(limit): # Goes 0 to limit-1 ... # Correct: Include limit for a in range(limit 1): # Goes 0 to limit ... # Also correct: Use min(n, limit) for optimization for a in range(min(n, limit) 1): ...对应地C/Java 中应写a aMax而非a aMaxGo 的for a : 0; a maxA; a与 Rust 的0..max_a闭区间也体现了同一约定。陷阱三容斥符号错误容斥的核心是交替符号0 个违规为加、1 个违规为减、2 个为加、3 个为减。若误写成全加结果会明显偏大# Wrong: All additions for j in range(4): res C3[j] * ways # Should alternate signs! # Correct: Alternating signs based on j for j in range(4): sign 1 if j % 2 0 else -1 res sign * C3[j] * ways五种解法横向对比解法核心思想时间复杂度空间复杂度适用场景暴力枚举三重循环 等式判定$O(l^3)$$O(1)$离线验证基准、小数据自测两重循环剪枝确定c只检查上界$O(\min(n, l)^2)$$O(1)$直观改进中等数据Enumeration I合法b构成连续区间直接计数$O(\min(n, l))$$O(1)$单变量枚举的标准写法Enumeration II显式rem 2l提前剪枝$O(\min(n, l))$$O(1)$同 I语义更清晰容斥原理隔板法闭式解 交替加减违规项$O(1)$$O(1)$竞赛正解$n, l$ 可达 $10^9$从暴力到容斥的演进路径本身就是一条通用方法论能确定一个变量就消掉一层循环 → 剩余变量的合法值构成区间就直接计数 → 计数公式本身可用闭式表达就用容斥把约束剥掉。这套推理可以平移到「把n分给k个变量且每个不超过limit」的同类受限整数划分问题此时隔板项变为 $\binom{mk-1}{k-1}$容斥求和上界也变为k。小结本文以仓库文档 articles/distribute-candies-among-children-ii.md 为骨架完整复现了 Leetcode 2994 的五个解法阶段$O(l^3)$ 暴力、$O(\min(n,l)^2)$ 剪枝、两种 $O(\min(n,l))$ 区间计数以及 $O(1)$ 容斥正解并逐条落实了原文档的三个实现陷阱C 的下界遗漏、循环边界 off-by-one、容斥符号。每种解法均给出 Python / Java / C / Go / Rust 等语言的实现与 64 位整型的防溢出要点其余语言版本JavaScript、C#、Kotlin、Swift可直接在原文档的 Tab 代码块中取用该仓库同时维护了python/、java/、go/、cpp/、rust/等多语言解题目录便于按语言风格交叉参考同类组合计数问题的写法。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考