两数之和
描述
给定一个整数数组 nums 和一个目标值 target，在数组中找出和为目标值的那两个整数，返回他们的数组下标。
假设每种输入只会对应一个答案。但同一个元素不能使用两次。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
Go 语言实现
双重遍历
思路双重遍历确认两个数之和为 target 即可。注意第二个数从第一个数的后面元素遍历即可。
func TwoSum1(nums []int, target int) []int {
// # 双重遍历
//O(n^2), O(1)
l := len(nums)
for i, a := range nums {
// 计算 当前元素和后续元素的和进行比较
for j:=i+1; j<l; j++ {
if a + nums[j] == target {
return []int{i, j}
}
}
}
return []int {}
}
使用 map 存储补数
补数：若 a + b = target，那么在 target 下 a 和 b 互为补数。
思路，使用 map 结构，存储 key 为遍历值的 补数，而值对应值的索引。遍历时，判断是否存在该数的补数，若存在，找到答案！
func TwoSum2(nums []int, target int) []int {
// # map 结构，在 map 中保存 补数 进行测试
// O(N), O(N)
vIdx := map[int]int{}
for i, n := range nums {
// 判断 n 的补数是否存在
if idx, exists := vIdx[n]; exists {
if i < idx {
return []int {i, idx}
} else {
return []int {idx, i}
}
}
// 以补数作为 key 存储补数及对应的索引
vIdx[target - n] = i
}
return []int {}
}
本题来自于 Leetcode，在提交中表现如下：
执行用时 :4 ms, 在所有 golang 提交中击败了97.39%的用户
内存消耗 :3.7 MB, 在所有 golang 提交中击败了45.21%的用户
更多内容请访问或关注 红牛慕课， 红牛慕课
