http://inder-gnu.blogspot.com/2007/10/find-two-nos-in-array-whose-sum-x.html

2)

have 2 pointers

p1=start of an array

p2=end of array

a[p1]+a[p2] > x then p1++

else a[p1] + a[p2] < x then p2++

else return p1 and p2

1) use hashmap

Here is a little dry run of array a= {1,2,3,4,5,6,7,8} and sum = 6.

6 – 1 = 5 — found in Hashtable H ? No – store it in H. H will contain (1)

6 –2 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2)

6 –3 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2, 3)

6 –4 = 2 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (4,2)

6 –5 = 1 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (5,1)

Advertisements