企业官网建设流程全解析

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一节列出了三个前置知识点，下面结合本问题的具体用法逐一说明：

1. 组合学基础（Combinatorics Basics）：不带上限约束时，求非负整数方程a + b + c = n的解的个数，属于经典「隔板法」（Stars and Bars）问题——n个球与 2 块隔板排成一排，共有C(n+2, 2) = (n+2)(n+1)/2种摆法。这个闭式表达式是整个解法体系的基石。
2. 枚举技巧（Enumeration Techniques）：系统地遍历所有合法取值组合，并用min(n, limit)这类上界收紧循环范围、用「确定一个变量后其余变量取值落在区间内」代替内层循环。
3. 容斥原理（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)$，必然超时——它的价值在于提供一个可以离线验证其他解法正确性的基准。

算法步骤

1. 初始化计数器res = 0；
2. 三重嵌套循环遍历每个孩子可能的糖果数（0到limit，含limit本身）；
3. 对每组(a, b, c)，检查a + b + c == n；
4. 成立则res += 1；
5. 返回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 res

public 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 a+b+c == 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)。

算法步骤

1. 初始化res = 0；
2. a从0循环到min(n, limit)；
3. 对每个a，b从0循环到min(n - a, limit)；
4. 令c = n - a - b，若c <= limit（此时c >= 0由内层上界保证），计数器加一；
5. 返回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 res

public 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时），内层循环被彻底消掉。

算法步骤

1. 初始化res = 0；
2. a从0循环到min(n, limit)；
3. 对每个a，计算b_max = min(n - a, limit)与b_min = max(0, n - a - limit)；
4. 若b_max >= b_min，把(b_max - b_min + 1)累加进计数器；
5. 返回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 res

public 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分支检查被显式化，语义更清晰（两种写法时间复杂度相同，但剪枝条件在极端输入下能少做无用计算）。

算法步骤

1. 初始化res = 0；
2. a从0循环到min(n, limit)；
3. 令rem = n - a，若rem > 2 * limit则跳过本次迭代；
4. 否则合法(b, c)配对数为min(rem, limit) - max(0, rem - limit) + 1，累加进res；
5. 返回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 res

public 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{m+2}{2} = \frac{(m+2)(m+1)}{2}$$

不加约束时（j = 0）总方案数为 $\text{ways}(n)$。接下来逐层处理「某个孩子超过limit」（即拿到 $\geq limit + 1$ 颗）的违规情形：

• 1 个孩子超限：任选一个孩子（3 种选法），先给他塞limit + 1颗，剩余 $n - (limit+1)$ 颗仍按隔板法分配，违规数 $3 \cdot \text{ways}(n - (limit+1))$，需要减去；
• 2 个孩子超限：在上一轮被减了两次，容斥要求加回$3 \cdot \text{ways}(n - 2(limit+1))$（从 3 个孩子里选 2 个）；
• 3 个孩子超限：再加一次也要减，减去$\text{ways}(n - 3(limit+1))$。

合并起来就是统一的求和式：

$$\text{ans} = \sum_{j=0}^{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(limit+1) < 0$ 时该项无意义，直接跳过（continue）。求和只有 4 项，故时间复杂度 $O(1)$。

数值验证（可用此例自测实现）：n = 5, limit = 2时，暴力枚举可手验解仅为(2,2,1)的 3 种排列，答案为 3；代入容斥公式：j=0项 $\binom{7}{2} = 21$，j=1项 $-3 \times \binom{4}{2} = -18$，j=2,3项因 $m < 0$ 跳过，合计 $21 - 18 = 3$，与暴力结果一致。

算法步骤（对应原文档 Algorithm）

1. 定义二项系数：从m+2中选 2，即(m+2)*(m+1)/2；
2. j从0到3，计算m = n - j * (limit + 1)；
3. 若m < 0，跳过该项；
4. 计算ways = (m+2)*(m+1)/2；
5. 按容斥规律取交替符号（j为偶数取 +，奇数取 −），并乘以C3[j]；
6. 累加所有项，返回结果。

多语言实现

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 res

public 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$ 时(m+2)*(m+1)乘积溢出 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 + 1

b_min = max(0, n - a - limit)中的第二项正是把c ≤ limit反解到b上的结果。

陷阱二：循环边界的 Off-by-One

0与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 < aMax；Go 的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

五种解法横向对比

从暴力到容斥的演进路径本身就是一条通用方法论：能确定一个变量就消掉一层循环 → 剩余变量的合法值构成区间就直接计数 → 计数公式本身可用闭式表达就用容斥把约束剥掉。这套推理可以平移到「把n分给k个变量且每个不超过limit」的同类受限整数划分问题（此时隔板项变为 $\binom{m+k-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