Find a pair of elements from an array whose sum equals a given number

Question

Given array of n integers and given a number X, find all the unique pairs of elements (a,b), whose summation is equal to X.

The following is my solution, it is O(nLog(n)+n), but I am not sure whether or not it is optimal.

int main(void) {     int arr [10] = {1,2,3,4,5,6,7,8,9,0};     findpair(arr, 10, 7); } void findpair(int arr[], int len, int sum) {     std::sort(arr, arr+len);     int i = 0;     int j = len -1;     while( i < j){         while((arr[i] + arr[j]) <= sum && i < j)         {             if((arr[i] + arr[j]) == sum)                 cout << "(" << arr[i] << "," << arr[j] << ")" << endl;             i++;         }         j--;         while((arr[i] + arr[j]) >= sum && i < j)         {             if((arr[i] + arr[j]) == sum)                 cout << "(" << arr[i] << "," << arr[j] << ")" << endl;             j--;         }     } } 

Answer 1

There are 3 approaches to this solution:

Let the sum be T and n be the size of array

Approach 1:
The naive way to do this would be to check all combinations (n choose 2). This exhaustive search is O(n²).

Approach 2: 
 A better way would be to sort the array. This takes O(n log n)
Then for each x in array A, use binary search to look for T-x. This will take O(nlogn).
So, overall search is  O(n log n)

Approach 3 :
The best way would be to insert every element into a hash table (without sorting). This takes O(n) as constant time insertion.
Then for every x, we can just look up its complement, T-x, which is O(1).
Overall the run time of this approach is O(n).

You can refer more here.Thanks.

Answer 2

# Let arr be the given array. # And K be the give sum   for i=0 to arr.length - 1 do   # key is the element and value is its index.   hash(arr[i]) = i   end-for  for i=0 to arr.length - 1 do   # if K-th element exists and it's different then we found a pair   if hash(K - arr[i]) != i       print "pair i , hash(K - arr[i]) has sum K"   end-if end-for