【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 Table、Array

解題邏輯與實作

這一題算是 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. 解題目錄