Two Sum

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.

Example 1:

• Input: nums = [2,7,11,15], target = 9
• Output: [0,1]
• Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

• Input: nums = [3,2,4], target = 6
• Output: [1,2]

The brute force approach is simple. Loop through each element $x$ and find if there is another value that equals to $target - x$.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        // In case there is no solution, we'll just return null
        return null;
    }
}

We can use a HashMap to store the complement of the current number required to reach the target.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        var indexCompMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i ++) {
            if (indexCompMap.containsKey(nums[i])) {
                return new int[] {indexCompMap.get(nums[i]), i};
            }
            var comp = target - nums[i];
            indexCompMap.put(comp, i);
        }
        return new int[] {0, 0};
    }
}

Complexity Analysis

• Time Complexity: $O(n)$ where n is the number of elements in the array. We traverse the list containing $n$ elements only once.
• Space Complexity: $O(n)$. The extra space required depends on the number of items stored in the hash table.