问题是，给定一个数D和一个数量为N的数列，求其中差值最大且不超过值D的三个数的组合的数量。例如:
D = 3, N = 4
Sequence of numbers: 1 2 3 4
Possible combinations: 1 2 3 (3-1 = 2 <= D), 1 2 4 (4 - 1 = 3 <= D), 1 3 4, 2 3 4.
Output: 4
我做了什么:link
我的概念是:遍历整个数字序列，找到与当前比较数字相减时超过 D 值的最小数字。然后，找到这两个数字之间的组合，当前比较的数字是一个固定值(这意味着 n [两个数字之间的数字] 的组合取 2)。如果当前比较的数减去序列中最大的数不超过D，则用全数取3的组合。
N最大为10^5，最小为1，D最大为10^9，最小为1。
我的算法有问题:当我组合第一个元素和第 10^5 个元素时发生溢出。我怎样才能解决这个问题？有没有一种方法可以在不实际执行阶乘的情况下计算大量组合？
编辑:
发生最坏情况时会发生溢出:当前比较的数字仍在索引 0 中，而所有其他数字在与当前比较的数字相减时仍然小于 D。例如，索引 0 处的数字的值为 1，索引10^5处的number的值为10^5 + 1，D为10^9。然后，我的算法将尝试计算 10^5 - 0 的阶乘，然后溢出。阶乘将用于计算 10^5 取 3 的组合。
最佳答案
当您在排序列表中查找值范围D 中的项目，并得到索引差异M 时，您应该计算C(M,3)。
但是对于这样的组合数你不需要使用巨大的阶乘:
C(M,3) = M! / (6 * (M-3)!) = M * (M-1) * (M-2) / 6
进一步减少中间结果:
A = (M - 1) * (M - 2) / 2
A = (A * M) / 3
关于algorithm - 找出满足特定要求的序列中三个数字的组合数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54675076/