題目連結: Two Sum

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

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

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

• 複雜度評估
  設有 n 個數，任取兩數的組合數為 $C_2^n = \frac{n(n-1)}{2}$， 所以時間複雜度為 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 各有優劣，我們一般會採用時間複雜度較低的解法。

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