给小朋友们分糖果 II

You are given two positive integers n and limit.

Return the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.

 

Example 1:

Input: n = 5, limit = 2
Output: 3
Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).

Example 2:

Input: n = 3, limit = 3
Output: 10
Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (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) and (3, 0, 0).

 

Constraints:

• 1 <= n <= 106
• 1 <= limit <= 106

/*
 * 思路：
 * 使用 Java Stream API，我们可以通过流的方式处理糖果的分配。利用 IntStream 来枚举每位小朋友分到的糖果数，
 * 并通过过滤条件筛选出符合要求的组合。最后通过计数来获取满足条件的总方案数。
 */

import java.util.stream.IntStream;

public class Solution {
    public long countWays(int n, int limit) {
        return IntStream.rangeClosed(0, Math.min(limit, n)).boxed()
            .flatMap(i -> IntStream.rangeClosed(0, Math.min(limit, n - i)).boxed()
            .filter(j -> n - i - j >= 0 && n - i - j <= limit)
            .map(j -> new int[]{i, j, n - i - j}))
            .count();
    }
}

这个题解使用了容斥原理来计算分配糖果的总方案数。首先定义一个辅助函数 c2(n)，它计算从 n 个不同元素中选择 2 个元素的组合数，即 n * (n - 1) / 2。对于给定的 n 和 limit，我们可以将问题转化为计算总方案数，然后减去不合法的方案数（即某个小朋友得到的糖果数超过 limit）。具体来说，总方案数为从 n + 2 个不同元素中选择 2 个元素的组合数（相当于给每位小朋友分配 0 到 n 颗糖果，再减去两个额外的'边界'元素）。不合法的方案数可以通过容斥原理计算，即减去每位小朋友得到超过 limit 颗糖果的方案数，加上每两位小朋友都得到超过 limit 颗糖果的方案数，再减去所有三位小朋友都得到超过 limit 颗糖果的方案数。

O(1)

O(1)