1. 两数之和

一、题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

二、思路

1. 第一种思路

这种方法比较粗暴并且很笨了。首先用目标值减去数组中的第一个（下标为0）的元素，然后判断差值是否在数组剩余元素num[1:]中。如果在，得到结果；如果不在，然后再用目标值减去第二个元素，判断差值是否在数组num[2：]…..。就这样直至得到结果。

2. 第二种思路

利用哈希表，数组中的元素的值与对应的下标作为键值映射。然后用目标值依次与数组中的元素做差，然后差值作键在哈希表中获取对应的下标，返回最终结果。

三、代码实现

1. 第一种思路

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(nums)
        for i in range(length):
            diff = target - nums[i]
            if diff in nums[i+1:]:
                # 获取第二个数在切片数组中的下标
                index = nums[i+1:].index(diff)
                return [i, index + i + 1]
        return []

        # 下边用try...except写的
        length = len(nums)
        for i in range(length):
            diff = target - nums[i]
            # 不再用if判断diff是否在数组中
            try:
                # 获取第二个数在切片数组中的下标
                index = nums[i+1:].index(diff)
            except:
                pass
            else:
                return [i, index + i + 1]
        return []

2. 第二种思路

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = {}
        length = len(nums)
        for i in range(length):
            diff = target - nums[i]
            if hashmap.get(diff) is not None:
                return [hashmap.get(diff), i]
               else:
                hashmap[nums[i]] = i
        return []

四、结果

方法	运行时间	击败	内存消耗	击败
第一种：if…in..	680ms	49%	13.1MB	79%
第一种：try…except…	752ms	49.54%	13.1MB	90.42%（疑惑）
第二种	16ms	99.20%	13.5MB	31.53%