这是LeetCode题库中的第一题。一个从数组中找到一对相加等于目标数的数的算法。文中我们使用了两种不同的方法来实现我们的算法。
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].Solution 1. 暴力遍历 O(n^2) :
使用for 循环遍历 时间复杂度为O(n^2)
func twoSum(nums []int, target int) []int {
for i := 0; i < len(nums); i++ {
for l := i + 1; l < len(nums); l++ {
if nums[l]+nums[i] == target {
return []int{i, l}
}
}
}
return []int{}
}
Solution 2. 使用Map. O(n)
使用了Map键和值对应的特性。Map可以用key来快速检索数据。如果一个key存在于Map中，则会返回值。如果不存在，则不会。所以我们能够通过使用当前数值和目标数值之间的差值，快速的求得我们当前需要的数字是哪一个，并将之作为key放入Map中去查找。如果不存在，则将当前数字和索引，分别作为key和value放入map中。
func twoSum2(nums []int, target int) []int {
buff := make(map[int]int)
for i, num := range nums {
val, ok := buff[target-num]
if ok {
return []int{val, i}
}
buff[nums[i]] = i
}
return nil
}
