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

问题很简单，有一个数组和一个数字，问题就是这个数组中有多少组元素之和能得到这个目标数字。

这个问题面试过程中会被经常问到，算是烂大街的问题了，当然相应的变种题目还有就是：如果数组中有重复数字怎么办？数组中的数字已经排序了怎么办？当然这些问题就都是在后续可以看到。

最容易想到的就是暴力遍历两次数组，那可是O(N^2)的算法，必然不行，还有一种就是使用哈希的算法，这样就不需要考虑去重：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for i, n in enumerate(nums):
            if n in d:
                return [d[n], i]
            d[target - n] = i

这样就把问题简化到O(1)。当然，如果看到数组是排序好了的，而且有重复元素，这个时候可以如果需要把全部的结果都拿到，就可以用双指针的方法，先排序，一个指针在头元素，另一个指针在尾元素，这类题目算是该题目的变形，在后续也可以看得到。