如何计算 i,j,k 的三元组使得 i < j < k

Question

我想知道计算三元组i、j、 等k计数的有效方法i < j < k。

我尝试使用以下代码：

for i in range(n):
  for j in range(i + 1, n):
    for k in range(j + 1, n):
      ans += 1

但这会导致 O(N ³ ) 时间复杂度，而且效率不高。O(N log N) 时间复杂度（或更快）将是最佳的。

Answer 1

你不需要任何循环。有一个封闭形式的公式：

或者：