前言
平生不識TwoSum，刷盡LeetCode也枉然。
歡迎開啟LeetCode刷題的旅程，這將是一段漫長而又艱辛的旅程。不過一定要牢記的是，不要下船，不要中途放棄，要堅持。
這道Two Sum的題目作為LeetCode的開篇之題，乃是經(jīng)典中的經(jīng)典，正所謂‘平生不識TwoSum，刷盡LeetCode也枉然’
環(huán)境以及工具
- Python 3.7.2
- PyCharm 2018.3.3
擼起袖子就是干
題目：
給定一個整數(shù)數(shù)組 nums 和一個目標值 target，請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù)，并返回他們的數(shù)組下標。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，你不能重復(fù)利用這個數(shù)組中同樣的元素。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
思路一
擼起袖子就是干！暴力求解，兩重循環(huán)。由于兩重循環(huán)，所以時間復(fù)雜度：O(n2)，注意觀察可以看出并沒有創(chuàng)建多余的臨時空間，空間復(fù)雜度為：O(1)
暴力解法
def twoSum(self, nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
思路二
一般來說，我們?yōu)榱颂岣邥r間的復(fù)雜度，需要用空間來換。思路二中我們使用python中的字典來存儲，字典中用鍵-值(key-value)存儲給定的數(shù)組，字典具有常數(shù)級產(chǎn)找效率，類似java中的hashmap。這樣，我們在遍歷數(shù)組的時候，用target減去遍歷到的數(shù)字，就是另一個需要的數(shù)字了，直接在字典中查找其是否存在即可。還有一點需要注意，遍歷到的數(shù)字所在的位置不能和字典中位置一樣。例如：target=4,num(0)=2,dict(0)=2。
時間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)
兩遍哈希表法
def twoSum2(self, nums, target):
hashdict = {num: index for index, num in enumerate(nums)}
for i, num in enumerate(nums):
complement = target - num
if complement in hashdict and i != hashdict[complement]:
return [i, hashdict[complement]]
思路三
一遍哈希表就ok了，一個for循環(huán)搞定。這里我就不展開說了。
這次還特意學(xué)了python相關(guān)語法，打完收工，舒服。
獻上我的Github的鏈接，下載代碼即可運行，歡迎star
https://github.com/cb858504/PythonLearningTravel
