Find two numbers that add up to target

Question

I am trying to solve this problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

and this is my implementation:

public int[] twoSum(int[] numbers, int target) {
 Map<Integer, Integer> numbersMap = new HashMap<Integer, Integer>();
 int[] requiredNumbers = null;
 int index = 0;
 for (int number : numbers) {
 if (numbersMap.containsKey(target - number)) {
 requiredNumbers = new int[2];
 requiredNumbers[0] = numbersMap.get(target - number);
 requiredNumbers[1] = index;
 return requiredNumbers;
 } else {
 numbersMap.put(number, index);
 index++;
 }
 }
 return requiredNumbers;
}

How can I improve its execution time?

• Ankit Soni: you could have used indexed for loop as you are anyway keeping the track of the index

Answer 1

If the size of your input array can be large, you can get a speed-up by preallocating the capacity of your HashMap:

Map<Integer, Integer> numbersMap = new HashMap<Integer, Integer>(numbers.length * 2);

As the algorithm runs, data will be added to the HashMap. When number of entries exceeds the capacity * load_factor, the hashmap's capacity is doubled, and the elements are re-binned for the larger capacity. This capacity doubling and rebinning takes time. It doesn't happen often, \$O(\log N)\$ times, but it can be eliminated by starting with a hashmap of sufficient capacity.

The load_factor defaults to 0.75, so an initial capacity larger than numbers.length * 4/3 is required. numbers.length * 2 is a simple expression that satisfies that requirement.