Two Sum

Problem

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

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

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

Brute force O(n^2) time and O(1) space

public class Solution {
    public 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 IllegalArgumentException("No two sum solution"); 
    }
}

HashMap solution O(n) time O(n) space

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) map.put(nums[i], i);
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            //Second condition is to avoid using same number twice 
            if (map.containsKey(complement) && map.get(complement) != i) return new int[] {i, map.get(complement)};
        }
        throw new IllegalArgumentException("Two two sum solution");
    }
}

Optimal one loop solution of above O(n) time and O(n) space

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) return new int[] {i, map.get(complement)};
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("Two two sum solution");
    }
}

Analysis

The first brute force solution is quite straightforward
The second and third solution use HashMap to store num as key and index as value
Since it's two sum, we loop through the nums to find out the another number's index (complement index)
Notice that, if there are duplicated number, the value will be updated and it does not matter
Ex, if there are two same numbers, and they are two sum, it will still return correct result
If there are more than two same numbers, they cannot be two sum, cause the problem guarantees only one solution
We don't need to check map.get(complement) != i in the third solution because we add new number at the end