解
由于我的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<=H O(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(L-b[i]); // search for largest number <= L-b[i] int max_index = binary_search(H-b[i]); // search for smallest number >= H-b[i] total += max_index - min_index + 1; // NOTE: This does not handle edge cases like not finding any sums that work}return total;
