Question

给定一个数和一个数组，在数组中找到两个值之和为给定数，显示所有情况，要求复杂度为O（n）;

请给出代码和解释

Answer 1

首先对数组进行排序，时间复杂度为（N*log2N）。

然后令i = 0，j = n-1，看arr[i] + arr[j] 是否等于Sum，如果是，则结束。如果小于Sum，则i = i + 1；如果大于Sum，则 j = j – 1。这样只需要在排好序的数组上遍历一次，就可以得到最后的结果，时间复杂度为O（N）。两步加起来总的时间复杂度O（N*log2N），下面这个程序就利用了这个思想，代码如下所示：

int getSumNum(int[] arr,int Sum)，   //arr为数组，Sum为和   
{  
    int i,j;  
    for(i = 0, j = n-1; i < j ; )  
    {  
        if(arr[i] + arr[j] == Sum)  
            return ( i , j );  
        else if(arr[i] + arr[j] < Sum)  
            i++;  
        else  
            j--;  
    }  
    return ( -1 , -1 );  
}

它的时间复杂度是O（N）。

刚开始一直无法理解这样一定可以找到这个和吗？难道不会漏掉了解的位置。可以这么理解，假如排好序后的数组为1,3,6,a,9,12,17,28,b,35,46  ,那么i最初指向1的位置，j最初指向46的位置，比如所求的是Sum=a+b，a<b，a和b在数组中的某位置上。那么i和j在变化过程中，只考虑i遇到了a或者j遇到了b的时候，必定有一个先遇到，比如i遇到了a，那么这个时候j必定还没指到b，故这时j指到的值比b大，从而j减小直到b位置。同理若j先指到了b位置，那么i必定还没指到a(这是我们的前提)，然后i现在指到的值比a小，故i增加，直到a位置。