[LeetCode] 1. Two Sum

---

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].

---

<br />

Method 1 Brute Force

The requirement is pretty simple and straightforward as we can just find out whether target - num[i] is the array or not; therefore, the simplest way is to Brute-Force this by iterating every possible value in the array.

And I will pass the code for this method for its low time-efficiency.
<br />

Method 2 HashTable

To achieve better time efficiency, we should use a hash table to store the array of integers in order to quickly find out the target number.

For every num[i], we have to find target - num[i] in the hash table, since the mechanism of storing numbers in hash table, we can reduce the look up time to from O(1) to O(n) instead of O(n^2).

Code are followed as below.

Java

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 subside = target - nums[i];

           if (map.containsKey(subside) && map.get(subside) != i) {
                return new int[] { i, map.get(subside) };
           }
    }
    throw new IllegalArgumentException("No such solution");
}

Complexity Analysis

Time Complexity: O(n).
In fact, we have to go through all n numbers exactly twice to find the solution.
Space Complexity: O(n).
<br />

Method 3 One-pass Hash Table

The procedure to store every number into hash map is unnecessary as we can combine these two steps into one action. We can first look up in the current hash map to find whether the matched answer is already in the map, if not, then we can add the number into the hash map.

The code is only slightly changed from the code above.

Java

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

    for (int i = 0; i < nums.length; i++) {
        int subside = target - num[i];

        if (map.containsKey(subside)){
            return new int[] { map.get(subside), i };
        }
        else{
            map.put( num[i], i );
        }
    }
     throw new IllegalArgumentException("No such solution.");
}

Complexity Analysis

Time Complexity: O(n).
Space Complexity: O(n).