优雅的实现数组中和为0的对数

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 思考

我们在写代码的时候可能考虑的更多的是怎样把功能实现。但是对于一个程序员来说，功能的实现仅仅是必要和最基础的条件，最终要写出高效的代码，对算法的研究也是必须要考虑的 如果是三个数或者四个数，我们也可以用此种方法，那么算法的复杂度应该是n^2*lgn,n3*lgn,大家可以自己去实现