iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 2
2
自我挑戰組

LeetCode演算法刷題 使用Go系列 第 2

Day02-[LeetCode演算法刷題 使用Go] -Two Sum

題目連結: Two Sum

題目描述為給定一個數組 (nums) ,跟一個目標數 (target),要在數組內找出兩數 a,b 滿足 a+b=target,並返回 a,b 在數組中的 index。
題目還有補充說明,此題我們可以多做一個假設: 總是可以找到唯一解,以及禁止使用數組中同一個元素兩次 。有了此假設我們就不必考慮無解的情形。

思路 1: 窮舉法(暴力法)

把任取兩數相加的所有可能都進行嘗試,看是否為目標數 (target)。

  • 複雜度評估
    設有 n 個數,任取兩數的組合數https://chart.googleapis.com/chart?cht=tx&chl=C_%7B2%7D%5E%7Bn%7D%3D%5Cfrac%7Bn(n-1)%7D%7B2%7D , 所以時間複雜度為 O(n²) 。而此方法所需記憶體與 n 無關, 空間複雜度為 O(1)。

參考程式碼:

func twoSum(nums []int, target int) []int {
  
    for i:=0;i<len(nums);i++{
        for j:=i+1;j<len(nums);j++{
            if nums[i]+nums[j]==target{
                return []int{i,j}
            }
        }
    }
    
    return []int{-1,-1}
}

思路 2: Hash 法

此題我們可以建立一組映射關係 (map) 來對應數字 v 與 index。從頭開始按順序查找,當搜索到數字 v 時,便去查找 map 中有沒有 (target-v),若有則滿足題目要求,可以返回此兩數的 index 。若沒有,則把 v 及其對應的 index 存到 map 中,繼續往後查找。

  • 複雜度評估
    該演算法至多只需要查找 n 個數,所需要的時間複雜度為O(n)。
    而此方法需要另外另外儲存 n 個數的對應 map ,空間複雜度為 O(n)。

參考程式碼:

func twoSum(nums []int, target int) []int {
  
    m:=make(map[int]int)
    
    for i,v:=range nums{
        
        j,exist := m[target-v]
        
        if exist{
            return []int{i,j}
        }
        
        m[v]=i
    }
    
    return []int{-1,-1}
}

小結

解法 1 與 2 各有優劣,我們一般會採用時間複雜度較低的解法。

附上簡單的測試,程式碼 在此。


上一篇
Day01-[LeetCode演算法刷題 使用Go] -基本介紹
下一篇
Day03-[LeetCode演算法刷題 使用Go] -Reverse Integer
系列文
LeetCode演算法刷題 使用Go30

1 則留言

1
一級屠豬士
iT邦大師 1 級 ‧ 2020-09-02 08:21:37

若能夠有完整可執行的程式碼,另外再加上測試的部分,測試含有benchmark,
是不是會更好?

ahero0963 iT邦新手 5 級 ‧ 2020-09-02 21:54:50 檢舉

你好,已在文章最後補上程式碼連結。

這樣蠻好的喔.

我要留言

立即登入留言