【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:

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

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




解題邏輯與實作

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

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


暴力法

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

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 所對應的索引值,與當前索引值合併成一個陣列回傳。



程式碼

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



[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

用Markdown寫Blogger文章

【Vue.js 學習筆記】02. 基礎 Vue 概述