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&lt;Integer, Integer&gt; numbersMap = new HashMap&lt;Integer, Integer&gt;();
    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?
If the size of your input array can be large, you can get a speed-up by preallocating the capacity of your HashMap:

Map&lt;Integer, Integer&gt; numbersMap = new HashMap&lt;Integer, Integer&gt;(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.