【LeetCode】0001. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].


Related Topics: Hash TableArray



解題邏輯與實作

這一題算是 LeetCode 中的 Hello World 吧,網路上還流傳著平生不識 TwoSum,刷盡 LeetCode 也枉然這句話呢,可見這題是多麼的廣為人知(?)

簡單來說這題是要從給定陣列中找出兩個數字,其總和為給定的 target,最後返回這兩個數字的索引值。每題必定只有一個解,且每個數字並不會被重複使用。


暴力法

最直覺想到的當然是暴力法,但果不其然 Time Limit Exceeded,畢竟用暴力法的時間複雜度是 $O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
   def cal_sum(self, num_1 , num_2):
      return num_1 + num_2

   def twoSum(self, nums, target):
      size = len(nums)
      for idx1 in range (size) :
         num_1 = nums[idx1]

      for idx2 in range(idx1+1 ,size):
         num_2 = nums[idx2]

         s = self.cal_sum(num_1,num_2)
         if s == target:
            return [idx1,idx2]

         raise RuntimeError("No two sum solution") 


雜湊表(Hash table)

既然暴力法時間複雜度爆表,那就拿空間換取時間吧!另外設立一個 HashMap 儲存走訪過的結果,當一個數字進來後去檢查差值是否存在 HashMap 中,若存在則回傳結果,實做步驟如下:

  1. 讀入陣列中一值 n,並計算其差值 diff = target - i
  2. 檢查差值 diff ,是否存在於 HashMap 中,
    1. 不存在,將 n 與所對應的索引值作為 key–value pair,存入 HashMap 中。
      • 因為,題目要求最後回傳的結果是兩個數字的索引值,所以必須一併紀錄索引值。
    2. 存在,則取出差值 diff 所對應的索引值,與當前索引值合併成一個陣列回傳。
1
2
3
4
5
6
7
8
9
class Solution:
   def twoSum(self, nums, target):
      keys = {}
      for idx, value in enumerate(nums):
         diff = target - value
         if diff in keys:
            return [keys[diff], idx]

         keys[value] = idx



其他連結

  1. 【LeetCode】0000. 解題目錄