【教3妹学编程-算法题】给小朋友们分糖果 II

3妹：1 8得8，2 8=16， 3 8妇女节…
2哥 : 3妹，在干嘛呢
3妹：双11不是过了嘛， 我看看我这个双十一买了多少钱， 省了多少钱。
2哥 : 我可是一分钱没买。
3妹：我买了不少东西， 衣服、包包、化妆器……， 接下来的一个月只能吃土了， 还要2哥救助~
2哥：你没有用花呗或信用卡吗， 把支付方式重新排列一下， 用最晚还款的那种信用卡，这样就可以暂时不用吃土啦。
3妹：可是后面还是要还信用卡啊。哎， 天下要有免费的午餐该有多好啊
2哥 : 傻啊你， 后面就发工资了啊， 不就缓解了
3妹：咦，有道理啊
2哥：说到免费的午餐，我今天看天一个免费的糖果的题目，我们来做一下吧~

题目：

给你两个正整数 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个小朋友，考虑分给第一个小朋友i个糖果，那么i的取值范围是[0, min(limit, range)], 此时还剩下left = n - i 个糖果，分给2个小朋友。
考虑left分成两份，位 j 和 left-j 每份的取值范围都需要满足要求。分三种情况：
left > 2limit, 此时无法满足条件。
left <= limit, 此时 j取[0, limit]均可，有limit+1种方法
left > limit 且 left/2 <= limit, 这个时候因为两个人是对称的，只需考虑第一个人的取值范围，也就是[n-limit, limit]，共limit-(n-limit) + 1 = 2limit - n + 1种
所以枚举i, 然后对left分情况讨论，一次遍历拿到结果。

java代码：

class Solution {public long distributeCandies(int n, int limit) {return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1);}private long c2(int n) {return n > 1 ? (long) n * (n - 1) / 2 : 0;}
}