# Find two numbers that add up to target

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?

• you could have used indexed for loop as you are anyway keeping the track of the index – Ankit Soni Dec 23 '18 at 18:24

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.