元组数量

我给了N个数a [1..N]和另外2个整数L和H.我如何计算满足i <j <k且L <= a [i] +的元组数（i，j，k） a [j] + a [k] <= H.

1 <= T <= 100 1 <= N <= 1000 1 <= L <= H <= 1000000 1 <= a[i] <= 1000000 

PS：需要比N2logn更好的解决方案

Answer 1

解

由于我的C / C ++有些生疏，这主要是一个算法问题，我将用伪代码编写（大多数是正确的C / C ++，其中包含一些算法需要一段时间才能写出来）。

如果你至少有sizeof（int）* 10 ^ 12字节的内存和可用时间，你可以使用时间复杂度为O（n ^ 2 * log（n））的算法。

 // Sort the N numbers using your favorite, efficient sorting method. (Quicksort, mergesort, etc.) [O(n*log(n))]. int[] b = sort(a) int[] c = int[length(b)^2]; // Compute the sums of all of the numbers (O(n^2)) for(int i = 0; i < length(b); i++){ for (int j = i; j < length(b); j++){ c[i*length(b)+j] = b[i]+b[j]; } } // Sort the sum list (you can do the sorts in-place if you are comfortable) - O(n^2*log(n)) d = sort(c); // For each number in your list, grab the list of of sums so that L<=num+sum<=HO(n) // Use binary search to find the lower, upper bounds O(log(n)) // (Total complexity for this part: O(n*log(n)) int total = 0; for (int i = 0; i < b; i++){ int min_index = binary_search(Lb[i]); // search for largest number <= Lb[i] int max_index = binary_search(Hb[i]); // search for smallest number >= Hb[i] total += max_index - min_index + 1; // NOTE: This does not handle edge cases like not finding any sums that work } return total; 

Answer 2

基本方法：

 for (i=0; i 

可能更好（可能有一个错误，但如果你已经超过最大值，基本的想法是打破）：

 for (i=0; i H) continue; for (j=i+1; j H) continue; for (k=j+1; k 

Answer 3

 int find_three(int arr[], int c, int l,int h) { int i, j, e, s, k; int count =0; sort(arr,arr+c); c--; while(arr[c]>h) c--; int sum=0; for (int i = 0; i<=c-2;i++) { sum=arr[i]+arr[i+1]+arr[i+2]; if(sum>h) break; for(j=i+1;j<=c-1;j++) { for(k=j+1;k<=c;k++) { sum=arr[i]+arr[j]+arr[k]; if(sum>=l &&sum<=h) count++; if(sum>h) break; } if(sum>h) break; } } return count; }