问题

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

Notice: You may assume that each input would have exactly one solution.

Example: numbers=[2, 7, 11, 15], target=9 return [1, 2]

Either of the following solutions are acceptable:
O(n) Space, O(nlogn) Time
O(n) Space, O(n) Time

思路

如果采用brute-force的话，对每一个数组中的元素A[i]，需要检查它后面的每一个元素A[j]是否满足A[i] + A[j] == target （0 <= i <= len(A)-1, i <= j <= len(A)-1)，时间复杂度为O(n^2)，空间复杂度为O(1)。

要将复杂度优化为线性，需要将检查每个元素的复杂度降为O(1)。自然而然就会想到Hash。由于需要返回元素的索引，而不是元素的值，我们需要用dict来记录元素和索引的对应关系。

在检查每个元素时，只需要检查其差值是否在dict中即可，复杂度为O(1)。总体的时间复杂度为O(n)，空间复杂度为O(n)。

代码

class Solution:
    """
    @param numbers : An array of Integer
    @param target : target = numbers[index1] + numbers[index2]
    @return : [index1 + 1, index2 + 1] (index1 < index2)
    """
    def twoSum(self, numbers, target):
        # write your code here
        if not numbers:
            return [-1, -1]
        num_dict = dict(zip(numbers, range(len(numbers))))
        for i, num in enumerate(numbers):
            diff = target - num
            if diff in num_dict:
                return [i+1, num_dict[diff]+1]
        return [-1, -1]