Two Sum

Question

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

Tags

• Array
• Hashmap

Thought

Two solutions:

• Brute force search
• Hashmap

The implementation of brute force search was skipped here, because it is very straightforward. However, the efficiency is very low and the time complexity is O(N^2).

Thus, we use hashmap here. Looping through the whole array, use the target - nums[i] as the key and the index i as the value to store the pair in the dictionary. The time complexity is O(N).

Code

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        counter = dict()
        for i in xrange(n):
            if nums[i] in counter:
                return [counter[nums[i]], i]
            else:
                counter[target - nums[i]] = i