在满足特定需求的序列中找到三个数字的组合量。

Question

问题是，给定一个数字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 

我所做的：链接

我的概念是:遍历整个数字序列，并在减去当前比较数时，找到超过D值的最小数。然后，找出这两个数字之间的组合，目前比较的数字是一个固定的值(这意味着两个数字之间的n个数的组合2)。如果即使序列中的最大数字与当前比较的数字相减也不超过D，则使用所取3的全部元素的组合。

最小的是1，N可以大到10^5，最小的是1，D也可以大到10^9。

算法的问题:当我对第一个元素和10^5元素进行组合时，会发生溢出。我怎么才能解决这个问题？有没有一种方法可以计算出大量的组合，而不需要实际的阶乘？

编辑：

当发生最坏的情况时会发生溢出:当前比较数字仍在索引0中，而所有其他数字(与当前比较的数字相减)仍然小于D。例如，索引0处的数字值为1，索引10^5处的数字值为10^5 + 1，D值为10^9。然后，我的算法将尝试计算10^5 - 0的阶乘，然后溢出。将用阶乘计算取3的10^5的组合。

Answer 1

当您在排序列表中查找值范围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

Answer 2

您没有将C++标记添加到您的问题中，所以让我用Python3编写答案(应该很容易将其转换为C++)：

N = int(input("N = "))
D = int(input("D = "))
v = [int(input("v[{}] = ".format(i))) for i in range (0, N)]

count = 0
i, j = 0, 1
while j + 1 < N:
    j += 1
    while v[j] - v[i] > D:
        i += 1
    d = j - i
    if d >= 2:
        count += (d - 1) * d // 2  # // is the integer division

print(count)

这样做的目的是将三元组j的上部索引向上移动，同时在最大距离j-i=d ( v[j]-v[i]<=D )处拖动较低的索引i。对于每个i-j对，都有保持j固定的1+2+3+...+d-1可能三元组，即(d-1)*d/2。