NOTES · 学习笔记
两数之和:从暴力循环到哈希表
题目
先讲一下哈希。HashMap 是一种基于哈希表的数据结构,用于存储键值对(key-value)。通俗易懂地说,HashMap 就是一个超级快的字典。回到题目:给定整数数组 nums 和目标值 target,找出和为 target 的那两个整数,返回它们的下标。比如 nums = [2,7,11,15]、target = 9,因为 nums[0] + nums[1] == 9,返回 [0,1]。
看到题目,很多人的第一反应是暴力解法:两层循环,第一个数和后面的每个数相加,等于 target 就返回。以 nums = [2,7,11,15]、target = 9 为例,过程就是 2+7=9(正确)、2+11=13、2+15=17、7+11=18、7+15=22、11+15=26。
时间复杂度 O(n²)。如果数组有一万个数,就要计算接近五千万次,显然不够优秀。
这时就要重新思考:遍历一次,当你看到 2 时,你知道你需要的数字是 7——也就是说不是找两个数,而是每个数都在找它需要的那个数:2 需要 7,7 需要 2,11 需要 -2,15 需要 -6。于是问题变成:我怎么知道这个需要的数字之前有没有出现过?准备一个 map(值 → 下标)开始遍历。第一步,2 需要 7,map 里有没有 7?没有,把 2 放进去,变成 {2:0}。第二步来到 7,它需要 2,map 里有 2 吗?有!说明 2+7=9,直接返回 [0,1] 结束。整数数组只遍历了一遍,时间复杂度 O(n)。
暴力解法的代码:
// 暴力解法:循环遍历两次判断值
func twoSum(nums []int, target int) []int {
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i]+nums[j] == target {
return []int{i, j}
}
}
}
return nil
}哈希表的写法。再用 [3,2,4]、target=6 走一遍:i=0,nums[i]=3,need=3,找不到,把 m[3]=0 存起来;i=1,nums[1]=2,need=4,找不到 4,把 m[2]=1 存起来;i=2,need=2,去 map 里查,找到了之前保存的下标 1——返回 []int{index, i}。
func twoSum(nums []int, target int) []int {
m := make(map[int]int) // 创建一个哈希表,用来保存数字、下标的映射
for i := range nums { // 遍历数组中的每一个元素
need := target - nums[i] // 计算当前数字需要的另一个数
index, ok := m[need] // 查询哈希表中是否存在需要的数
if ok {
return []int{index, i} // 存在则返回切片:index 之前数字的下标,i 当前数字的下标
} else {
m[nums[i]] = i // 不存在,保存当前数字下标和值进哈希表
}
}
return nil
}