Two Sum

发布时间:2020-06-16 11:00:19
阅读量:57
作者:猎维人工智能培训
算法面试题

题目描述

给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是多少?

分析与解法

答案:O(n)

思想类似于两端向中间扫描

1、设定两个指针P1、P2,分别指向数组开始和结尾,即P1指向最小值,P2指向最大值;

2、计算 *P1+*P2 的值为 SUM,与 sum 比较,记录它们的差值 DIF 和 SUM,若 SUM < sum,P1++,若 SUM > sum,P2--;

3、重复以上过程直到DIF最小


但如果数组是无序的呢?

如果数组是无序的,先排序(n*logn),然后用两个指针i,j,各自指向数组的首尾两端,令i=0,j=n-1,然后i++,j--,逐次判断a[i]+a[j]?=sum,如果某一刻a[i]+a[j]>sum,则要想办法让sum的值减小,所以此刻i不动,j--,如果某一刻a[i]+a[j] < sum,则要想办法让sum的值增大,所以此刻i++,j不动。所以,数组无序的时候,时间复杂度最终为O(n*logn+n)=O(n*logn)。


当然,如果原数组是有序的,则不需要事先的排序,直接O(n)搞定,且空间复杂度还是O(1)。

所以,如果有序,直接两个指针两端扫描,时间O(N),如果无序,先排序后两端扫描,时间O(N*logN+N)=O(N*logN),空间始终都为O(1)。


换言之,不论原序列是有序还是无序,解决这类题有以下三种办法:

1、对每个a[i],二分查找sum-a[i]是否也在原始序列中,若无序,则先排序后二分,时间复杂度总为O(n*logn),空间复杂度为O(1);

2、扫描一遍X-S[i] 映射到一个数组或构造hash表,时间复杂度为O(n),空间复杂度为O(n);

3、两个指针两端扫描(若无序,先排序后扫描),时间复杂度最后为:有序O(n),无序O(n*logn+n)=O(n*logn),空间复杂度都为O(1)。

所以,要想达到时间O(N),空间O(1)的目标,除非原数组是有序的(指针扫描法),不然,当数组无序的话,就只能先排序,后指针扫描法或二分(时间n*logn,空间O(1)),或映射或hash(时间O(n),空间O(n))。时间或空间,必须牺牲一个,自个权衡。


综上,若是数组有序的情况下,优先考虑两个指针两端扫描法,以达到最佳的时(O(N)),空(O(1))效应。否则,如果要排序的话,时间复杂度最快当然是只能达到N*logN,空间O(1)则是不在话下。


//代码一 

//O(N) 

Pair findSum(int *s,int n,int x)    

{    

   //sort(s,s+n);  如果数组非有序的,那就事先排好序O(N*logN)    

     

   int *begin=s;    

   int *end=s+n-1;    

     

   while(begin < end)   //俩头夹逼,或称两个指针两端扫描法,很经典的方法,O(N)   

   {    

       if(*begin+*end>x)    

       {    

           --end;    

       }    

       else if(*begin+*end < x)    

       {    

           ++begin;    

       }    

       else   

       {    

           return Pair(*begin,*end);    

       }    

   }    

     

   return Pair(-1,-1);    

}    

 

//或者如下编写, 

//代码二 

//copyright@ zhedahht && yansha 

//July、updated,2011.05.14。 

bool find_num(int data[], unsigned int length, int sum, int& first_num, int& second_num) 

{    

   if(length < 1) 

       return true; 

     

   int begin = 0; 

   int end = length - 1; 

     

   while(end > begin) 

   { 

       long current_sum = data[begin] + data[end]; 

         

       if(current_sum == sum) 

       { 

           first_num = data[begin]; 

           second_num = data[end]; 

           return true; 

       } 

       else if(current_sum > sum) 

           end--; 

       else 

           begin++; 

   } 

   return false; 

 

更多资讯