[LeetCode] 每日一题 2929. 给小朋友们分糖果 II（分类讨论 + 简单计算）

题目描述

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

题目链接

https://leetcode.cn/problems/distribute-candies-among-children-ii

示例输入

示例 1

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

提示

• 1 <= n <= 10^6

• 1 <= limit <= 10^6

解题思路

这题的本质是一个简单的枚举 + 分类讨论问题。我们要把 n 颗糖果分给三位小朋友，并且要求每人最多不能超过 limit 颗糖果，问总共有多少种分配方式。

因为糖果总数和人数都不大，我们可以直接枚举第一位小朋友分到的糖果数 i，范围从 0 到 min(n, limit)。然后对于剩下的糖果 res = n - i，我们再考虑第二个和第三个小朋友的分配方式：

• 如果 res <= limit，说明可以把剩下的糖果完全分给第二个人或第三个人，合法方案就是 [0, res] 的整数区间，共有 res + 1 种

• 如果 res > 2 * limit，说明无论怎么分都至少有一个人超过限制，直接跳过

• 否则，合法分法就是 (res - limit) 到 limit 之间的整数个数，方案数就是 (2 * limit - res + 1)

整题思路就是对第一个人暴力枚举，然后对后两人用区间分类计算合法解，逻辑清晰，复杂度也很低，属于那种一遍过但写起来挺舒服的题 😄

代码实现

class Solution {
    public long distributeCandies(int n, int limit) {
        long ans = 0;
        for (int i = 0; i <= Math.min(n, limit); i++) {
            int res = n - i;
            if (res > 2 * limit) {
                continue;
            } else if (res <= limit) {
                ans += res + 1;
            } else {
                ans += (2L * limit - res) + 1;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(min(n, limit))

  • 只枚举第一个人的分法，其余两个通过数学计算直接得出 🧮

• 空间复杂度：O(1)

  • 没有额外空间开销，一次遍历变量累加即可 🚀

总结

这题整体思路不复杂，但非常锻炼分类讨论和边界思维的能力。像这种限制条件明确、变量较少的问题，用枚举+数学组合的方式往往是最直接有效的。也是我比较喜欢的那类“简洁但考察思维清晰度”的题目之一🫠🫠

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。