給定一個(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]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有蹬音。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)上煤，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
解法一 暴力法
兩層循環(huán)遍歷所有可能的組合著淆，當(dāng)兩數(shù)和等于target時(shí)返回
時(shí)間復(fù)雜度
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums) - 1):
for j in range(i+1, len(nums)):
if target == (nums[i] + nums[j]):
return [i, j]
解法二 Hash法
遍歷每個(gè)元素劫狠，用字典保存target減當(dāng)前元素的結(jié)果和當(dāng)前索引
- 如果 字典 內(nèi)存在與當(dāng)前元素值相等的key 時(shí)，返回key對(duì)應(yīng)的value及當(dāng)前索引
- 否則永部，將 (target - value): 索引 作為 鍵: 值對(duì) 存入字典
典型的空間換時(shí)間的算法
遍歷一次即可独泞，每一次循環(huán)的操作時(shí)間復(fù)雜度是，因此總的時(shí)間復(fù)雜度是
苔埋，空間復(fù)雜度是
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
_dict = {}
for i, num in enumerate(nums):
if num in _dict.keys():
return [_dict[num], i]
else:
_dict[target - num] = i
