解题思路

思路1：

暴力方法

循环遍历两次，找出和为target的两个数

时间复杂度为O(N^2)

golang代码示例：

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums) - 1; i++ {   // 注意边界，i只需要遍历到倒数第二个数
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

思路2：

题目要求的是找出数组中的两个数之和等于target的两数下标，比如 a + b == target。我们反过来想问题，target - a == b即就是使用target去减数组中的每个元素，然后看判断数组中是否存在b。在这里我们可以使用一个map来存储数组的值以及对应的下标，这样判断b是否在数组中的时间复杂为O(1)。

因为要遍历一遍数组，所以最终的时间复杂度为O(n)

golang代码示例：

func twoSum(nums []int, target int) []int {
    Map := make(map[int]int, len(nums))
    // 构建Map，key-value -> nums[i]-i
    for i := 0; i < len(nums); i++ {
        Map[nums[i]] = i
    }

    for i := 0; i < len(nums); i++ {
        diff := target - nums[i]

        _, ok := Map[diff]
        if ok && Map[diff] != i {  // 其中判断不等于i是为了避免同一个元素使用两遍
            return []int{i, Map[diff]}
        }
    }
    return nil
}  

对上面代码的一个优化，使用一次迭代：

在将数组中的每个元素添加到Map中之前，可以先判断一下Map中是否有目标元素与当前元素的差值，如果有则返回对应的下标。

golang代码示例：

func twoSum(nums []int, target int) []int {
    Map := make(map[int]int, len(nums))
    // 构建Map，key-value -> nums[i]-i
    for i := 0; i < len(nums); i++ {
        diff := target - nums[i]
        if _, ok := Map[diff]; ok {
            return []int{i, Map[diff]}
        }
        Map[nums[i]] = i
    }
    return nil
}