問題
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)症见，并返回他們的數(shù)組下標(biāo)堪置。
你可以假設(shè)每種輸入只會對應(yīng)一個(gè)答案。但是盏筐，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素围俘。
示例：
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路過程
第一次接觸LeetCode，感覺這題真的是非常簡單琢融。兩次遍歷這個(gè)數(shù)組，求和就可以解決這個(gè)問題了簿寂。
class Solution(object):
def twoSum(self, nums, target):
for i, x in enumerate(nums):
for j, y in enumerate(nums):
if i == j:
pass
else:
if x+y == target:
return i, j
提交后發(fā)現(xiàn)漾抬，解答超時(shí)了，這時(shí)候常遂，才開始真正的去思考纳令，應(yīng)該如何提升效率。
上面的代碼很明顯，每次都額外判斷了i==j平绩，把這個(gè)判定稍微修改一下圈匆。
class Solution(object):
def twoSum(self, nums, target):
for i, x in enumerate(nums):
for j, y in enumerate(nums):
if x+y == target:
if i != j:
return i, j
這樣簡單修改了一下，發(fā)現(xiàn)提交通過了捏雌，解題時(shí)間花了4000+ms跃赚，似乎還有更大的提升空間。
遍歷hash表的效率是比遍歷數(shù)組的效率高的性湿，因此我們可以把第二次遍歷數(shù)組改為hash表纬傲。
class Solution(object):
def twoSum(self, nums, target):
dicts = {}
for i, x in enumerate(nums):
dicts[x] = i
for i, x in enumerate(nums):
if (target-x) in dicts:
if i != dicts[(target-x)]:
return i, dicts[target-x]
以上，代碼結(jié)構(gòu)和思路沒有變化肤频，只是把數(shù)組替換成hash表叹括，但是解題時(shí)間從4000+ms縮短為58ms
結(jié)語
第一次接觸LeetCode，突然發(fā)現(xiàn)這些題目做完之后宵荒，可以優(yōu)化我們平時(shí)寫代碼的習(xí)慣汁雷。
