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?

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

AJNeufeld · Accepted Answer · 2018-12-23 19:55:20Z

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.

Stack Exchange Network

Find two numbers that add up to target

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Find two numbers that add up to target

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions