2Sum problem Given an unsorted array of integers A 2 13 8 3

2-Sum problem:

Given an unsorted array of integers A = {2, 13, 8, 38, 63, 9, 11, 4, 1, 3} and a target sum Sum = 17

Goal:Using a hash implementation, determineif there exists two integers x, y in A such that x + y = Sum

Assume that there is only one solution to the sum. & Please use hash implementation for this. Thank you.

Solution

This can be done in O(n) using a hash table. Initialize the table with all numbers in the array, with number as the key, and frequency as the value. Walk through each number in the array, and see if (sum - number) exists in the table. If it does, you have a match. After you\'ve iterated through all numbers in the array, you should have a list of all pairs that sum up to the desired number.

array = initial array

table = hash(array)

S = sum

for each n in array

    if table[S-n] exists

        print \"found numbers\" n, S-n

The case where n and table[S-n] refer to the same number twice can be dealt with an extra check, but the complexity remains O(n).

            Let us say that we want to find two numbers in the array A that when added together equal N.

1.         Sort the array.

2.         Find the largest number in the array that is less than N/2. Set the index of that number as lower.

3.         Initialize upper to be lower + 1.

4.         Set sum = A[lower] + A[upper].

5.         If sum == N, done.

6.         If sum < N, increment upper.

7.         If sum > N, decrement lower.

8.         If either lower or upper is outside the array, done without any matches.

9.         Go back to 4.

The sort can be done in O(n log n). The search is done in linear time.

This is in Java

private static int[] intArray = {2, 13, 8, 38, 63, 9, 11, 4, 1, 3};

private static int sum = 17;

private static void algorithm()

{

    Map<Integer, Integer> intMap = new Hashtable<Integer, Integer>();

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

    {

        intMap.put(i, intArray[i]);

        if(intMap.containsValue(sum - intArray[i]))

            System.out.println(\"Found numbers : \"+intArray[i] +\" and \"+(sum - intArray[i]));

    }

    System.out.println(intMap);

}