准备定期刷一刷LeetCode上的题目，并且做一做笔记，这是第一篇。算法实现将采用Go语言。

1. 题目

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].

2. 中文分析

给予一个包含整数的数组和一个目标值，返回数组其中两个相加等于目标值的成员的下标。

3. 解答

3.1 解法1

暴力解法

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

这个解的Runtime是: 85 ms
时间复杂度：O(n^2)

3.2 解法2

通过go语言的map来做，相当于哈希表来做。

func twoSum(nums []int, target int)[]int {
    m := make(map[int]int, len(nums))
    for k, v := range nums {
        m[v] = k
    }

    for i, v := range nums {
        complement := target - v
        if j, ok := m[complement]; ok && j!=i {
            return []int{j, i}
        }
    }

    return nil
}

这个解的Runtime是: 10 ms
时间复杂度：O(n)

3.3 解法3

类似于解法2，解法先生成map，而解法3一边对比一边生成，效率上差别不大

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

    return nil
}

这个解的Runtime是: 9 ms
时间复杂度：O(n)