两数之和twoSum

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

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

---

• 解法一：
  根据targe - nums[i]的值，判断差值是否在nums[]里面。如果在，则需要判断获取的数和nums[i]是否相等。不相等就通过获取该值得索引值，并输出[ i, j ]，反之继续循环。
  tip：我们可不可以缩小每次判断差值 in nums[]这个列表的大小，来减少判断的时间呢？（以下列出了优化解法）

def twoSum( nums, target):
        i, j = 0, -1
        for x in nums:
            sub = target - x
            items = nums[i+1:]#通过切片获取更小范围的列表，缩小判断时间
            if sub in items:
                j = items.index(sub)+i+1#我们是从前往后查询的，最后索引值要加上i+1
                break
            i = i + 1
        if j >= 0:
            return[i, j]
        else:
            return[]

---

• 解法二：用字典模拟hash表，我们会使用到Python的内置函数enumerate（） 返回枚举对象

        hashmap = {}
        e_nums = list(enumerate(nums)) #把枚举对象转换成字典
        for index, value in e_nums:
            hashmap[value] = index #列表的值为key，索引为value
        for i, value in e_nums:
            j = hashmap.get(target - value)
            if (j is not None) and (j != i):
                return [i,j]

---

• 解法三：缩小需要查找的字典大小，来减少运行时间

def twoSum(nums, target):
    hashmap={}
    for i,num in enumerate(nums):
        if hashmap.get(target - num) is not None:
            return [i,hashmap.get(target - num)]
        hashmap[num] = i 
        #这句不能放在if语句之前，解决list中有重复值或target-num=num的情况

如果想要把hashmap[ num] = i放在前面，if判断中要添加 i !=hashmap.get(target - num)

---

---

done is better than perfect