In a given array of numbers find the pairs of numbers (x,y) that add up to a given sum s.

Question

You have an array a =[a1,a2,a3........an] and a number k.
You need to find the pairs that add up to k.

Example: a=[1,2,3,4,5,6] & k = 6
solution: (1,5);(2,4)

Answer 1

For each number i in array a, if a contains k-i, then add (i, k-i) to solution set. Repeat until i > k.

Answer 2

this is a naive solution and it takes O(n^2) to run it .

but interestingly a O(nlogn) solution exists.

1. First sort the array ------> O(n logn)
2. Run 1 iterator from beginning and one from end,
if the sum of the elements pointed is more than target, move the right iterator a step rleft
if the sum is less, move the left iterator a step right.
Keép iterating till a pair is found.------> O(n)