leetcode算法解析-1

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

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

示例:

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

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

1.暴力解决方法，遍历

class Solution():
    def twoSum(self, nums, target):
        for i in range(len(nums) - 1):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return (i,j)

2.利用python-dict的hash特点来实现O(1)复杂度的优解

2.1首先放出来这个错误的代码，理一下思路

class Solution2_bad():
    def twoSum(self, nums, target):
        hash = {}
        for index, num in enumerate(nums):
            hash[num] = index
            if target-num in hash:
                return (hash[target-num],hash[num])
        return None

这里的思路是：
dict的时间复杂度为O(1)，利用dict来存放数据，一次放一个，一旦找到解就返回退出
使用enumerate来枚举出index-num对
执行顺序是先放入后检查，测试了一组数据[2,4,6,7]-9似乎答案正确了，就提交了答案，结果就很惨
错误的原因：如果先放入第一组数据在碰到target=第一个数字*2的情况就会FAIL,因为不能使用重复的数字

2.1于是就改成下面这种解法

class Solution2():
    def twoSum(self, nums, target):
        hash = {}
        for index, num in enumerate(nums):
            if target - num in hash:
                return hash[target-num],index
            hash[num] = index

先检查后存入，这样就避免了2.1的疏漏，而且会比2.1少一次字典的插入
需要注意的是这时候返回的结果的第二个数字的下标就直接用index了，因为还没有存入字典中

另外有一个注意点，关于hash[target-num],index这两者的先后顺序
由于target-num是在字典中查找，所以一定是先插入到了字典中，所以下标会小