Medium

题目描述

给你两个正整数 n 和 limit。

返回将 n 个糖果分发给 3 个孩子的总方案数，使得每个孩子获得的糖果数不超过 limit 个。

示例 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 个糖果分发给 3 个孩子的方案数，每个孩子最多获得 limit 个糖果。

思路分析：

我们可以枚举第一个孩子获得的糖果数量 i，范围为 [0, min(n, limit)]。对于固定的 i，剩下要分配给第二、三个孩子的糖果数为 n - i。

设第二个孩子获得 j 个糖果，则第三个孩子获得 n - i - j 个糖果。约束条件为：

  • 0 <= j <= limit
  • 0 <= n - i - j <= limit

从第二个约束条件可得：n - i - limit <= j <= n - i

结合第一个约束条件，j 的有效范围为： max(0, n - i - limit) <= j <= min(limit, n - i)

如果这个范围有效（即左边界 <= 右边界），则对于当前的 i，有效的 j 的个数为： min(limit, n - i) - max(0, n - i - limit) + 1

将所有有效的 i 对应的方案数累加即可得到答案。

复杂度优化： 虽然可以直接枚举，但考虑到 n 和 limit 可能很大（最大 10^6），我们也可以使用数学公式进一步优化，但直接枚举在约束范围内也是可行的。

代码实现

class Solution {
public:
    long long distributeCandies(int n, int limit) {
        long long result = 0;
        for (int i = 0; i <= min(n, limit); i++) {
            int left = max(0, n - i - limit);
            int right = min(limit, n - i);
            if (left <= right) {
                result += right - left + 1;
            }
        }
        return result;
    }
};

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        result = 0
        for i in range(min(n, limit) + 1):
            left = max(0, n - i - limit)
            right = min(limit, n - i)
            if left <= right:
                result += right - left + 1
        return result

public class Solution {
    public long DistributeCandies(int n, int limit) {
        long result = 0;
        for (int i = 0; i <= Math.Min(n, limit); i++) {
            int left = Math.Max(0, n - i - limit);
            int right = Math.Min(limit, n - i);
            if (left <= right) {
                result += right - left + 1;
            }
        }
        return result;
    }
}

/**
 * @param {number} n
 * @param {number} limit
 * @return {number}
 */
var distributeCandies = function(n, limit) {
    let result = 0;
    for (let i = 0; i <= Math.min(n, limit); i++) {
        const left = Math.max(0, n - i - limit);
        const right = Math.min(limit, n - i);
        if (left <= right) {
            result += right - left + 1;
        }
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(min(n, limit))，需要枚举第一个孩子可能的糖果数量
空间复杂度O(1)，只使用常数额外空间

相关题目