Solution : Here is the idea is to start from the first element of the array and keep a Hashtable to store the potential pairs. We will check if sum – (a[i]) already exists in the Hashtable . If yes, we have a pair (a[i], value from Hashtable ) as the pair with the sum. If no, we store a[i] in the Hashtable .

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)

public static void TargetSum(int[] array, int target) { Dictionary<int, int> hashMap = new Dictionary<int, int>(); int lookup = 0; for (int i = 0; i < array.Length; i++) { lookup = target - array[i]; if (hashMap.ContainsKey(lookup) == true) { Console.WriteLine("Pair {0},{1}", lookup, array[i]); } else { hashMap.Add(array[i], array[i]); } } }

Filed under:
Array

Leave a comment