【Leetcode解題】1. Two Sum

題目

• 題目連結
• 目標函式 : twoSum(nums, target)
  • Input : nums: List[int]、target: int
  • Output : List[int]

解題概念

• 題意 : 給予一充滿各種不同數字的陣列 nums 與一數 target，需找出 nums 中兩個數字 nums[i] 與 nums[j]，兩者相加起來需等於 target，最後回傳 index list: [i, j]。
• nums 裡無重複之數字
• 要回傳之 index list 中的元素順序可為任意順序

我的寫法

• 想法 :
  1. 使用Hashmap tmap 去儲存閱覽過的元素
     • 儲存格式 : Key: 元素、Value: index({nums[i] : i})
  2. 使用 for 迴圈去閱覽 nums
     • 若 target - nums[i] 已儲存在 tmap 中 : 則回傳兩個元素的index
     • 若否 : 則將 {nums[i] : i} 加入 tmap 中
• 程式碼 :

  def twoSum(self, nums, target):
      
      tmap = dict()
      
      for i in range(len(nums)):
          if target - nums[i] in tmap:
              return [tmap[target - nums[i]], i]
          else:
              tmap[nums[i]] = i

• 成效 :
  • Time Complexity : $\color{DB4D6D}{O(n)}$
  • Runtime: 43 ms (faster than 83.21%)
  • Memory Usage: 14.3 MB (more than 23.15%)

解答 or 其他優秀寫法

• 皆與我的算法類似，時間複雜度也都是 $\color{DB4D6D}{O(n)}$