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

# 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

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.

Implementation in Java : Using codaddict's algorithm (Maybe slightly different)

import java.util.HashMap;

public class ArrayPairSum {


public static void main(String[] args) {        

    int []a = {2,45,7,3,5,1,8,9};
    printSumPairs(a,10);        

}


public static void printSumPairs(int []input, int k){
    Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();

    for(int i=0;i<input.length;i++){

        if(pairs.containsKey(input[i]))
            System.out.println(input[i] +", "+ pairs.get(input[i]));
        else
            pairs.put(k-input[i], input[i]);
    }

}
}

For input = {2,45,7,3,5,1,8,9} and if Sum is 10

Output pairs:

3,7 
8,2
9,1

Some notes about the solution :

• We iterate only once through the array --> O(n) time
• Insertion and lookup time in Hash is O(1).
• Overall time is O(n), although it uses extra space in terms of hash.