数组——两数之和

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

这里想的最直白的思路就是，遍历数组，然后用和减去我拿出来的这个数，看看剩下的那个数是否在剩下的数组中，如果在，在反向求出索引值。
毫无疑问，贼jb慢，因为涉及到多次列表查询和列表求索引。

别人最快的思路
遍历数组，用和减去拿出来的元素，然后把这个元素放到字典中并记录索引，因为遍历到后面的时候，一定可以发现一个元素和这个放入到字典中的元素一样，那个时候即可直接返回了。
整个算法的复杂度非常少。

答案(一)

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

答案(二)

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = {}
        for index, num in enumerate(nums):
            another_num = target - num
            if another_num in hashmap:
                return [hashmap[another_num], index]
            hashmap[num] = index
        return None