Problem description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

There are 2 possible solutions that I came up with in Java, let’s look at them and see how they work.

Full problem can be found here.

Solution 1

For the 1st solution I have come up with a dumb approach of iterating twice over the array and checking the elements. The problem with this approach is that it is not efficient having a time complexity of O(2n).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public static int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if ((nums[i] + nums[j]) == target) {
                return new int[]{i, j};
            }
        }
    }
    throw new RuntimeException("Something went wrong");
}

Solution 2

A more efficient approach is to have a HashMap, where we can check if hashMap.contains(currentNums - target). If it does contain it we can just return the HashMaps value, otherwise we will need to put the currentNum with its index in the HashMap. By doing this we need to iterate over the array only once, resulting in a time complexity of O(n).

See below for code snippet:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public static int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> numsHolder = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int subTarget = target - nums[i];
        if (numsHolder.containsKey(subTarget))
            return new int[]{numsHolder.get(subTarget), i};
        numsHolder.put(nums[i], i);
    }

    throw new RuntimeException("Something went wrong");
}

Conclusion

In conclusion while both solutions work and provide the right answer, the solution 2 is the recommended one, since it has the better time complexity of O(n).