LeetCode刷題_TwoSum(親測有效)

2020-10-25 12:00:47

LeetCode 第 1個問題:兩數之和

題目描述

給定一個整數陣列 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

此處用到了兩個迴圈

 
 

利用python中list相關函數解決

方法一:

解題思路:
找到num2 == target - num1 是否在list中,然後運用兩個方法:

  • num2 in nums 返回true說明成功
  • nums.index(num2) 查詢num2的索引

程式碼

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

  • 這個演演算法先用列表中的[2,7,11,15],9-2=7在字典中查詢7,但此時字典是空的,把2存入字典;
  • 然後再用9-7=2在字典中查詢,此時字典中已存入了一個2,找到了7和2的位置;
  • 在返回時return[dct[target - n],i] ,此時target - n為9-7=2,故先返回2的位置,再返回7的位置

 
 

小結

利用字典解決該問題最簡單,遍歷列表同時查字典,但也消耗了一定記憶體