題1：
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)瘫寝，并返回他們的數(shù)組下標(biāo)碴裙。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是陶缺，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素钾挟。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?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特點(diǎn)來(lái)實(shí)現(xiàn)O(1)復(fù)雜度的優(yōu)解
2.1首先放出來(lái)這個(gè)錯(cuò)誤的代碼饱岸，理一下思路
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的時(shí)間復(fù)雜度為O(1)掺出，利用dict來(lái)存放數(shù)據(jù)徽千，一次放一個(gè)，一旦找到解就返回退出
使用enumerate來(lái)枚舉出index-num對(duì)
執(zhí)行順序是先放入后檢查蛛砰，測(cè)試了一組數(shù)據(jù)[2,4,6,7]-9似乎答案正確了罐栈，就提交了答案黍衙，結(jié)果就很慘
錯(cuò)誤的原因：如果先放入第一組數(shù)據(jù)在碰到target=第一個(gè)數(shù)字*2的情況就會(huì)FAIL,因?yàn)椴荒苁褂弥貜?fù)的數(shù)字
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的疏漏，而且會(huì)比2.1少一次字典的插入
需要注意的是這時(shí)候返回的結(jié)果的第二個(gè)數(shù)字的下標(biāo)就直接用index了琅翻，因?yàn)檫€沒(méi)有存入字典中
另外有一個(gè)注意點(diǎn)位仁，關(guān)于hash[target-num],index這兩者的先后順序
由于target-num是在字典中查找，所以一定是先插入到了字典中方椎，所以下標(biāo)會(huì)小
