查找三胞胎与总和一个阵列中的一个范围内

-1

可能重复：
Number of tuples 查找三胞胎与总和一个阵列中的一个范围内

给定N个数字a[1..N]和2以外的整数L和H，我们要计数的元组的数目(i,j,k)这样L <= a[i] + a[j] + a[k] <= H。这可以做得比O(n^3)更好吗？任何建议/算法？

2012-11-04 Steve

这是如何与C++？ – jogojapan

一些大学有功课，因为星期一... http://stackoverflow.com/questions/13216041/number-of-tuples – Corbin

没有数字没有排序。 – Steve

首先按升序排序[i]。

枚举[i]和A [j]时，所以可以使用binary search找到[k]的多少满足L - （A [1] + A [j]）< = A [k]的< = H - （a [i] + a [j]）。

整个算法成本O(n^2*log(n))

2012-11-04 08:39:03 Topro

回答