兩數(shù)之和（two-sum）
這是LeetCode上一道十分經(jīng)典的題目，存在多種解法惦界，難度是簡單挑格，但后面難度更高的三數(shù)之和、四數(shù)之和沾歪，其實(shí)也是由這道題演變而來的漂彤。
題目
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)瞬逊，并返回他們的數(shù)組下標(biāo)显歧。你可以假設(shè)每種輸入只會(huì)對應(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）
鏈接：https://leetcode-cn.com/problems/two-sum
解題
方法一： 暴力法
暴力法很邏輯很簡單范删，采用兩輪錯(cuò)位嵌循環(huán)蕾域，計(jì)算兩個(gè)位置的數(shù)字之和是否等于目標(biāo)值，因?yàn)轭}目中說明了只有兩個(gè)整數(shù)的和是等于target到旦，所以一旦找到直接 return 就行旨巷，十分簡單粗暴。
class Solution(object):
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
這種寫法很好理解添忘，得益于Python語言的簡潔采呐，上面核心部分的代碼甚至可以簡化為一行：
chain.from_iterable([[i, j] for i in range(len(nums) - 1) for j in range(i + 1, len(nums)) if nums[i] + nums[j] == target])
因?yàn)槭乔短籽h(huán)，所以時(shí)間復(fù)雜度是O()搁骑，空間復(fù)雜度是O(1)斧吐，提交了也沒毛病，在所有 python 提交中擊敗了31.08%的用戶仲器，這種方法在運(yùn)行效率上不是很高煤率。面試時(shí)如果沒有太好的思路，可以嘗試用暴力法來解決乏冀。如果能在短時(shí)間內(nèi)寫出上面的代碼蝶糯，至少說明你對語言本身還是很熟練的，代碼的功底也還可以辆沦。
方法二：哈希大法
正確的思路是采取空間換時(shí)間的辦法昼捍，使用一個(gè)哈希表緩存识虚。思路如下：
題目要求我們找出兩個(gè)和為target的數(shù)，也就是
nums[i] + nums[j] = target妒茬。轉(zhuǎn)換一下舷礼，也就是
target - nums[i] = nums[j]。把nums[i]和i以鍵值對的形式存到哈希表中郊闯，注意存的是{值:下標(biāo)}這種格式 妻献。
由此可以看出，我們下次再遍歷nums的時(shí)候团赁，如果哈希表中存在一個(gè)數(shù)是target與當(dāng)前數(shù)的差育拨，那么那個(gè)數(shù)就是我們要找的數(shù)。而哈希表中查詢的時(shí)間復(fù)雜度是O(1)欢摄，所以整體函數(shù)的效率提高了一個(gè)數(shù)量級熬丧。
-
再一次循環(huán)nums，這次一邊循環(huán)一邊檢索第4步存儲(chǔ)的哈希表怀挠，如果能檢索到析蝴，說明符合條件，立即返回绿淋，over闷畸。這里面有一個(gè)小坑，如果有一個(gè)數(shù)n吞滞，target與n的差恰好也等于n佑菩，這樣就會(huì)在哈希表中查詢到n自己，顯示是不符合題目要求的裁赠，所以在判斷的時(shí)候要注意過濾掉殿漠。
代碼如下：
class Solution(object): def twoSum(self, nums, target): d = {n: i for i, n in enumerate(nums)} for i, n in enumerate(nums): # 在哈希表中查詢的時(shí)候，注意過濾掉當(dāng)前數(shù)自身 if target - n in d and d[target - n] != i: return i, d[target - n]方法二一共遍歷了兩次nums佩捞，時(shí)間復(fù)雜度為O(2N)绞幌，同時(shí)引入一個(gè)新的字典，空間復(fù)雜度變成了O(N)一忱，所以說是用空間換時(shí)間莲蜘。
方法三：優(yōu)化的哈希大法
方法二的其實(shí)還可以再優(yōu)化一下，只用遍歷一次nums就可以得到結(jié)果掀潮。在遍歷的同時(shí)把數(shù)據(jù)寫入哈希表中菇夸，并進(jìn)行查詢，這樣最壞的情況下時(shí)間復(fù)雜度也就是O(N)仪吧。
class Solution(object):
def twoSum(self, nums, target):
d = {}
for i in range(len(nums)):
if target - nums[i] in d:
return i, d[target - nums[i]]
d[nums[i]] = i
因?yàn)樵谧值渲胁樵兊臅r(shí)候庄新，當(dāng)前數(shù)字還沒有放到哈希表中，所以省去了一個(gè)判斷條件，代碼邏輯變的更加簡單择诈。
