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

Leetcode: English, Chinese

Solution

It’s easy to come out with the solution with $O(n^2)$ time complexity:

for num1 in array:
  for num2 in array:
    if (num2 == target - num1):
      return [num1, num2]

The nested loop is just for checking if the complement exists in the array, so we can use a hash map to reduce the look up time from $O(n)$ to $O(1)$. The map’s key is the number, the value is the number’s position.

We iterate each element of the array. If the current element’s complement already exists in the map, we have found a solution. Otherwise we insert the element into the map.

Code

Github (C++)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            if (map.count(target - nums[i]) == 0) map[nums[i]] = i;
            else {
                ans.push_back(map[target - nums[i]]);
                ans.push_back(i);
            }
        }
        return ans;
    }
};