可能重复: 元组的数
Possible Duplicate: Number of tuples
由于N个数 A [1..1]
和2等整数L和H,我们要算的元组(我数, J,K)
,使得 L< = A [1] + A [J] + A [K]< = H
。
能比更好地这样做为O(n ^ 3)
?
任何建议/算法?
Given N numbers a[1..N]
and 2 other integers L and H, we have to count number of tuples (i,j,k)
such that L <= a[i] + a[j] + a[k] <= H
.
Can this be done in better than O(n^3)
?
Any suggestions/ algorithms?
第一排序[I]增加订单。
first sort a[i] to increasing order.
枚举[I]和[J],这样你就可以使用二进制搜索以找到多少一[K]满足L - (A [I] + A [J])LT = A [K]&LT; = H - (A [I] + A [J]。)
enumerate a[i] and a[j], so you can use binary search to find how many a[k] satisfies L - (a[i] + a[j]) <= a[k] <= H - (a[i] + a[j]).
整个算法的成本为O(n ^ 2 *的log(n))