请教一道2sum的变种

刚面完的某小公司的一道题
Given an array of integers, return the number of pairs, each whose sum is less than or equal to a specific target.

E.g. input [3, 2, 5, 1, 0] and target = 5. The output should be 7.

很明显用两个for loop可解，是O(N^2)，但是如果想要O(NlogN)甚至O(N)的话应该怎么做呢?真心求教。。。



补充内容 (2019-1-18 01:44):
大家的回复都很给力，非常感谢！总结一下，首先要排序O(NlogN)，然后利用二分O(NlogN)，或者头尾双指针O(N)都行。因为排序O(NlogN)，所以整体至少O(NlogN)。

先排序， 时间复杂度O(nlogn)
然后利用单调性，检查累加和。两个指针分布指向数组两端。如果最小值+最大值满足小于等于target，那么最小值到最大值之间的所有数都满足<=target；因此可以继续统计次小值。
否则，说明右边数字太大，缩小一下试试。右侧指针永远不需要回到最右侧。两个指针相交之后，结束。因此总体时间复杂度O(n)

arrays.sort(arr);

l=0, r = arr.length-1;
while( l < r ){
   if( arr[l] + arr[r] <= target ) {
         count += r-l;  //例如 [l]=0, [r]=5,  [l]+[r] <= 5, 因此小于r的其他数字与l的累加都小于等于5
         l++; //检查稍大点的小数字
   }
   else{
        r--;
    }
}

=> count

我的想法是排序之后，头尾两个指针往中间靠

排序一遍然后每次二分找index累加 O(nlogn)
Target合理范围 记Count(n=k) 算Count(n <= k) 累加 O(max(N, Target))

O(nlogn)  sort 一下，利用单调性做;