# 0001. Two Sum

## [題目:](https://leetcode.com/problems/two-sum/)

哪兩個數相加等於`target`，回傳兩數所在的`index`。
最少且只會有一筆正確的答案。同一元素不能重複使用兩次。

> 測試資料:
>
> [2,7,11,15]
9
[3,2,4]
6
[3,3]
6
>
> 輸出:
[0,1]
[1,2]
[0,1]

## 思路一：暴力法、窮舉法
用雙迴圈把每種可能都加起來比較一次

func twoSum(nums []int, target int) []int {
    for i, n1 := range nums{
        for j, n2 := range nums{
            if i != j && n1 + n2 == target{
                return []int{i,j}
            }
        }
    }
    return nil
}

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 nil
}

## 思路二：用map記下這數字的索引位置
第一次迴圈：用map記下這數字的索引位置
第二次迴圈：再尋一次nums，尋找有無此元素的補數，有則讀出該補數的索引位置

func twoSum(nums []int, target int) []int {
    var m = map[int]int{}  
    for i, n := range nums{
        m[n] = i    // 記下這數字的索引位置
        // 因為一定會有一組解，數值相同的被後面值的索引蓋過去沒影響
    }
    for i, n := range nums{
    if j, ok := m[target-n]; ok && i != m[target-n]{
        // map中的key(target-n)有值，且元素不重複
            return []int{i, j}
        }
    }
    
    return nil
}

> 測試資料:
> [2,7,11,15], 9
>
> map的樣子:
key value
[2] = 0
[7] = 1
[11] = 2
[15] = 3

## 思路三：用map記下互補數字的索引位置
和思路二大同小異，只是又能省去一個迴圈
只用一次回圈，用map記錄下互補數（可以與本元素組成目標值的另一個數）的索引位置
在依序讀數字進來的當下，看一下map中目前有無互補數，
有則直接返回，沒有的話再加進map中，也能省去判斷元素重複使用的問題

func twoSum(nums []int, target int) []int {
    var complement = map[int]int{}  // complement 記錄此元素的補數（與target的差）
    for i, n := range nums{
        if j, ok := complement[n]; ok{
            return []int{i, j}
        }
        complement[target-n] = i    // key:補數 ; value:補數所在位置的索引
    }
    
    return nil
}

> 測試資料:
> [2,7,11,15], 9
>
> map的樣子:
key value
[7] = 0
[2] = 1
[-2] = 2
[-6] = 3

這解法真是腦洞大開啊！