給定一個整數陣列 nums
和一個目標值 target
,請你在該陣列中找出和為目標值的那 兩個 整數,並返回他們的陣列下標。
你可以假設每種輸入只會對應一個答案。但是,你不能重複利用這個陣列中同樣的元素。
範例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解題思路:利用兩個迴圈解決
程式碼
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range (len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i,j]
結果and總結
執行時間:6132ms 記憶體消耗:14MB
此處用到了兩個迴圈
解題思路:
找到num2 == target - num1 是否在list中,然後運用兩個方法:
程式碼
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums):
num1 = nums[i]
num2 = target - num1
if num2 in nums:
#如果num2=num1,且在nums中出現了一次,說明找到num1本身。
if(num1 == num2) & (nums.count(num2)==1):
continue
return[i,nums.index(num2,i+1)] #index(num2,i+1)是從num1後的序列找num2位置
結果and總結
執行時間:1148ms 記憶體消耗:14MB
此處用到了一個迴圈
解題思路:在方法一的基礎上,num2的查詢不需要每次從nums查詢一遍,可以按照切片的思想從num1之前或者之後查詢就行。這次從num1之前找.
程式碼
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(1,len(nums)):
temp = nums[:i]
num1 = target - nums[i]
if num1 in temp:
j = temp.index(num1)
return[j,i]
結果and總結
執行時間:408ms 記憶體消耗:13.8MB
這個演演算法先找到列表[2,7,11,15]中的7,再找到2;所以return[j,i]
時先返回j,再返回i
解題思路:利用字典模擬雜湊求解,遍歷列表同時查字典
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dct = {}
for i, n in enumerate(nums):
if target-n in dct:
return [dct[target - n], i]
dct[n] = i #構造字典
結果and總結
執行時間:48ms 記憶體消耗:14.6MB
return[dct[target - n],i]
,此時target - n
為9-7=2,故先返回2的位置,再返回7的位置
利用字典解決該問題最簡單,遍歷列表同時查字典,但也消耗了一定記憶體