-1

可能重复：
元组数

给定 N 个数字a[1..N]和 2 个其他整数 L 和 H，我们必须计算元组的数量，(i,j,k)使得L <= a[i] + a[j] + a[k] <= H. 这可以做得更好O(n^3)吗？有什么建议/算法吗？

4

1 回答 1

0

首先将 a[i] 排序为升序。

枚举a[i]和a[j]，所以你可以使用二分查找找到有多少a[k]满足L - (a[i] + a[j]) <= a[k] <= H - ( a[i] + a[j])。

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

于 2012-11-04T08:39:03.930 回答