1. Two Sum

Description

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

Solutions

　　终于要开始准备刷题了，一看到这个题目当然第一个想法就是看用什么语言了，毕竟平时写代码不是很多，而且一般用 Python 的情况平凡一些，于是还是不要打击信心尝试用 C++，想着还是先弄熟一门语言后再开始搞定另外一门吧。

　　看到这道题，一般人都很容易想到暴力求解法，能达到 $O(n^2)$ 的时间复杂度，这当然在面试中是不太能博得面试官的芳心的。

1. Brute Force

　　直接两层 for 循环来找对应的数值对，此时 Time Complexity 是 $O(n^2)$，Space Complexity 是 $O(1)$，总共耗时高达 4332 ms。

# Time: O(n^2)
# Space: O(1)
def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    # boundary conditions
    if len(nums) <= 1:
        return [-1, -1]
    
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    
    return [-1, -1]

　　同样是 Brute Force 的方法，但是只是调用了 Python 的 index 来定位也能有一点速度上的提升，以下代码在平台上用时 1380 ms。同样时间复杂度是 $O(n^2)$，空间复杂度是 $\mathcal{O}(n)$。

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    if len(nums) <= 1:
            return [-1, -1]
            
    dicts = dict(zip(range(len(nums)), nums))
    for key, value in dicts.iteritems():
        res = target - value
        if res in dicts.values() and key != dicts.values().index(res):
            return [key, dicts.values().index(res)]
        
    return [-1, -1]

2. One-pass Hash Table

　　对照暴力求解的方式是遍历一个数就扫描所有的互补数据选，那么我们可以将问题分解一下，首先遍历一遍所有的数字这是必不可少的，那么我们可以做文章的只有在找对应的互补数据的情况下了。为了加速搜索，我们一般会牺牲一点空间复杂度来换取较低的时间复杂度，于是我们用 Hash（即 Python 中的 dict）。如果我们先单独遍历一遍数据得到所有数据的互补数据并存到 dict 当中会有一个问题，如果发生了冲突就不太好存对应的位置了。于是就想到能不能一边遍历数据时一遍存当前数据的互补数据，因为即使有重复，我们只需要前面一个数据就好了，这里不用考虑重复组合的情况。那么我们就可以用如下的方式做，并得到了较好的效果 20 ms。

# Time: O(n)
# Space: O(n)
def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
        
    # boundary conditions
    if len(nums) <= 1:
        return [-1, -1]
        
    buff_dict = {}
    for i in range(len(nums)):
        if nums[i] in buff_dict:
            return [buff_dict[nums[i]], i]
        else:
            buff_dict[target - nums[i]] = i
    return [-1, -1]

References

1. Two Sum