Problem description:

Given an array of integers, find two numbers such that they add up to a specific target number.

Your function should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

You may assume that each input would have exactly one solution.

**Input:** numbers={2, 7, 11, 15}, target=9

**Output:** index1=1, index2=2

Solution:

There exist a very obvious quadratic solution, you would just need to loop through the array and for each i element loop from i +1 to n to look for the number which gives you a sum so that array[i] + array[j] = target. This approach works just fine but the problem is that it’s too slow, it runs in quadratic time O(n^2), could we do it better? Yes.

An optimized solution is to use an additional data structure which allows us to keep track of each number that we have and also its index, for this task we could use a HashMap which offers a constant time look-up operation, so we just need to loop the array once to store the elements and their corresponding indices in our HashMap and then loop through the array again and for each element i just check if hashmap.containsKey(target – array[ i ]). Here is the working solution implemented in Java:

public int[] twoSum(int[] numbers, int target) { HashMap<Integer, Integer> indexes = new HashMap<Integer, Integer>(); for(int i = 0; i < numbers.length; ++i) { indexes.put(numbers[i], i); } for(int i = 0; i < numbers.length; ++i) { if(indexes.containsKey(target - numbers[i])) { return new int[]{i + 1, indexes.get(target - numbers[i]) + 1}; } } return null; }

This solution is much faster than the first approach, this runs in linear time (considering that HashMap look-up operation runs in constant time).