leetcode - 两数之和

两数之和

问题描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定: nums = [2, 7, 11, 15], target = 9
因为: nums[0] + nums[1] = 2 + 7 = 9
返回: [0, 1]

链接：原题链接

两种解法

暴力求解

• 思路：

  func twoSum1(nums []int, target int) []int {
  	length := len(nums)
  	for index1, _ := range nums {
  		for index2 := index1+1; index2 < length ; index2++ {
  			if target == nums[index1] + nums[index2] {
  				return []int{index1, index2}
  			}
  		}
  	}
  	return nil
  }

  时间复杂度：O(N^2)
  空间复杂度：O(1)

使用 map 方法

• 思路: 遍历 nums 的元素 v ,判断 map[target - v]是否存在。若不存在，则以 v 为 key 存入到 map 中；若存在即完成查找。

  func twoSum2(nums []int, target int) []int {
  	m := map[int]int{}
  	for i, v := range nums {
  		if  k, ok := m[target - v]; ok {
  			return []int{k, i}
  		}
  		m[v] = i
  	}
  	return nil
  }

  时间复杂度：O(N)
  空间复杂度：O(N)