本文共 973 字，大约阅读时间需要 3 分钟。
Problem1: You have a lists with integers. Find all the pairs of numbers that sum less than or equal to to a particular number k. The list contains minimum 5 Million number.(I provided a n^2logn solution but they may be looking forward to having a better answer).
----------------------------------------------------------------------------------------
Problem2: Input - array of integers size N, integer Threshold. Output - the number of pairs (x, y) of distinct elements with condition x + y <= Threshold. Is that possible to implement it with O(n) ?
---------------------------------------------------------------------------------------
// perform radix sort - O(n). now the array is sorted Or quicksort, O(n) is difficult// now, remove duplicates if you wish. and now perform the following algorithmint i(0), j(n-1), ans(0);while (i < j){ if (a[i] + a[j] <= threshold ) { ans += (j-i); i++; } else { j--; } }return ans; 转载地址：http://nwboi.baihongyu.com/