1 问题需求
对于一个没有重复数字的数组，列如 int[] a= {-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10};如果求得和为0的整数对的数量。
2 方法一
遍历集合集合即可,代码如下
private int serach(int[] a){
int num =0;
for (int i=0;i<a.length;i++){
for (int j=i+1;j<a.length;j++){
if(a[i]+a[j]==0){
num++;
}
}
}
return num;
}
代码很简单，如果数组的量很大时，此算法的复杂度为n^2.能不能减少算法的发复杂度了？答案是肯定的
3 二分法实现
我们知道二分法的复杂度为lgn,比n小，下面我们用二分法将此算法的复杂度缩小到nlgn.
private int binarySearch(int[] a){
int num = 0;
for (int i=0;i<a.length;i++){
if(binarySearchRank(-a[i],a)>i){
num++;
}
}
return num;
}
//二分查找
private int binarySearchRank(int num, int[] array) {
int result = -1;
int start = 0;
int end = array.length-1;
while (start<end){
if(array[start] == num){
result = start;
break;
}
if(array[end] == num){
result = end;
break;
}
int middle = (start+end)/2;
if(array[middle]>num){
end = middle;
}else if(array[middle]<num){
start = middle;
}else {
result = middle;
break;
}
if(start+1==end){
result = -1;
break;
}
}
return result;
}
我们主要分析binarySearch(int[] a) 这个方法，这个方法里面有两层循环，第一层循环的复杂度为n,第二层循环的复杂度为二分法的复杂度，即为lgn.整体的复杂度为nlgn,比n^2效率又高了不少。接下来我们来分析，整个算法的思路。关键代码 binarySearchRank(-a[i],a)>i ，这一句是，我们遍历整个集合（最外层德尔循环），通过二分法查找，如果存在与这个数相反的数，就相当于存在这样一对和为0的数对。为什么要大于i了，因为主要是为了去重。如果直接写 binarySearchRank(-a[i],a)！=-1 ，那么当binarySearchRank(-1,a)与binarySearchRank(1,a)所查找的都是1与-1 这一对数字，会计算两次。当然如果都计算两次，在最后除以2也是可以的，但是这样的话，所用的时间会变为原来的两倍。
4 思考
我们在写代码的时候可能考虑的更多的是怎样把功能实现。但是对于一个程序员来说，功能的实现仅仅是必要和最基础的条件，最终要写出高效的代码，对算法的研究也是必须要考虑的 如果是三个数或者四个数，我们也可以用此种方法，那么算法的复杂度应该是n2*lgn,n3*lgn,大家可以自己去实现
