查找三胞胎與總和一個陣列中的一個範圍內

-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

回答