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

We can use brute-force directly

There’s one case to note when the input is

[3, 2, 4]
6

If i==j is not judged, the answer will end up being [0, 0], which is apparently wrong.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++) {
            for(int j = nums.length - 1; j >= 0; j--) {
                if(i == j) continue;
                if(nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        
        throw new IllegalArgumentException("No two sum solution");
    }
}

To avoid the collision of i and j, we can better write the solution like this

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[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        
        throw new IllegalArgumentException("No two sum solution");
    }
}

Other Solutions

Our ultimate goal is to find the complement of a number chosen. So for a chosen number, we can first calculate its complement and then try to find the complement from the list.

To make that process faster, we can implement a hash table. With the number as a key, and the original index as the data. After calculating the complement, we can query it directly from the hash table. The amortized query time is guaranteed to be O(1), although the construction time of the hash table is O(N) and it takes extra space.

Two-pass Hash Table

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];
        if(map.containsKey(complement) && map.get(complement) != i) {
            return new int[]{i, map.get(complement)};
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

One-pass Hash Table

In the previous implementation, there are 2 sequential loops, one for insertion and another for the query. To make it more efficient(although without significant improvement), we can try to find the complement as the insertion goes. In this way, only one loop is required.

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[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}