Optimization for the index of the pair in the array whose sum is specified

Question

I encode to find all the indices of a pair of numbers in an array whose sum is already given.

for(i=0;i<max;i++)
{
    for(j=i+1;j<max;j++)
    {
        if(a[i]+a[j]==sum)
            printf("%d %d\n",i,j);
    }
}

where max is the maximum size of the array. And the sum is the sum of a pair of numbers. (An array may have duplicate values.)

But I get only this naive O (n ^ 2) solution. Can anyone help me in getting the best solution for this case.

Answer 1

• Sort the array. O (NLG (n))

• for each iin your array O (n) for binary search sum-i O (lg (n)) for all O (nlg (n))

2 O (nlg (n)), O (nlg (n))

Answer 2

, :

j = max-1
for (i=0; i<j; i++) {
    while (a[i] + a[j] > sum and j>i) j--;
    if  (a[i] + a[j] == sum) printf("%d %d\n",i,j);
}