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

1. Brute Force

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

Time complexity: $O(n^2)$

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for x in range(len(nums) - 1):
            for y in range(x + 1, len(nums)):
                if nums[x] + nums[y] == target:
                    return x, y

2. Two-pass Hash Table

To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table. We reduce the look up time from O(n) to O(1) by trading space for speed.

A simple implementation uses two iterations. In the first iteration, we add each element's value and its index to the table. Then, in the second iteration we check if each element's complement target - nums[i] exists in the table.

新建一个hashmap，遍历数组，已知target和当前遍历到的数字，在hashmap中找是否存在对应的数字，如果有，返回两个数字索引，如果没有，把当前数字存入hashmap，继续遍历 。本题本质是“搜索”问题，所以要想到“搜索”常用的数据结构！！！以空间换时间。时间复杂度O(n)，空间复杂度O(n)（hash table）

把每个数作为 key，把每个值作为index

 class Solution(object):
    def twoSum(self, nums, target):
        hashmap={}
        for i in range(len(nums)):
            hashmap[nums[i]] = i
        for i in range(len(nums)):
            newnum = target - nums[i]
            if hashmap.has_key(newnum) and i != hashmap[newnum]:
                return i, hashmap[newnum]

3. One-pass Hash Table

class Solution(object):
    def twoSum(self, nums, target):
        hashmap = {}
        for i in range(len(nums)):
            newnum = target - nums[i]
            if nums[i] in hashmap:
                return hashmap[nums[i]],i
            else:
                hashmap[newnum] = i