Find the pair in array with condition

Question

Let say I have an array of Int, I want to find a pair of number in this array that the sum of this pair is equal to an number, like so:

func findPair(list: [Int], _ sum: Int) -> (Int, Int)? {
    for i in 0..<list.count - 1{
        for j in (i+1)..<list.count {
            let sumOfPair = list[i] + list[j]
            if sumOfPair == sum {
                return (list[i], list[j])
            }
        }
    }
    return nil
}

The first parameter is an array of Int, the second parameter is an number that we need to compare some pairs in that array.

For example:

findPair([1,2,3,4,5], 7) // will return (2, 5), because 2 + 5 = 7

But the complexity of this algorithm is O(n^2).

Is there any way faster?

Answer 1

Try the following approach:

sort(arr,arr+n);//Sort the array

low=0;

high=n-1; // The final index number (pointing to the greatest number)

while(low<=high)
{
   if(arr[low]+arr[high]==num)
   {        print(low,high);
            break;
    }
   else if(arr[low]+arr[high]<num)
         low++;
   else if(arr[low]+arr[high]>num)
         high--;

}

Basically, you are following the greedy Approach over here... Hope it works.. :)