【每日一算法】两数之和，使用map实现

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思考：
1. 数组？两个数之和？两个两个一组，双层循环遍历所有可能，判断之和是否相等，即可找出答案。
双层循环存在的问题，因为嵌套循环，所以时间负责度为O(N2)


func twoSum(nums []int, target int) []int {
  // 外层循环，遍历所有
  for i := 0; i < len(nums); i++ {
    // 内层循环，从上层循环的下一个开始遍历
    for j := i + 1; j < len(nums); j++ {
      // 如果相加的值等于target则成功找到并返回
      if nums[i]+nums[j] == target {
        return []int{i, j}
      }
    }
  }
  return []int{}
}


2. 使用map存储nums遍历过的值为key，下标为key的值，
如果map中存在target-当前遍历的值，则直接返回，
不存在则加到map中
这样，这样时间复杂度就变成了O（N）
func towSum(nums []int, target int) []int {
  // 初始化一个map
  result := make(map[int]int)
  // 开始循环
  for index, value := range nums {
    // 如果map中存在（target-nums中的当前值），则将下标返回
    if i, ok := result[target-value]; ok {
      return []int{i, index}
    } else {
      // 如果不存在，则将该值及下标存入map
      result[value] = index
    }
  }
  return []int{}
}