Leetcode-01 Two Sum

这是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
}