两数之和：哈希（LeetCode 热题 100）

一、问题描述二、解题代码解法一、暴力class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: n len(nums) for i in range(n): for j in range(i1,n): if nums[i]nums[j] target: s [i,j] return s解法二、哈希from typing import List class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: hash_dict {} # 空字典格式 {数字:下标} for idx, num in enumerate(nums): need target - num # 算出需要配对的数字 # 判断需要的数字之前有没有遍历到 if need in hash_dict: # hash_dict[need] 配对数字的下标 # idx 当前数字的下标 return [hash_dict[need], idx] # 没找到配对把当前数字和下标存入字典 hash_dict[num] idx小技巧字典【数字:下标】新建的字典中把需要的数字当作下标存储而该字典的值为原数列的下标。例i0, num2need7字典无 7 → 执行hash_dict[2] 0i1, num7need2字典存在 2 → 取出hash_dict[2]0直接得到答案为什么要存数字:下标查询速度极快字典查找是 O (1)暴力两层循环是 O (n²)反向存储把 “值” 作为 key下标作为 value通过目标差值反向定位历史下标避免二次循环每走一个元素只做一次减法 一次查表一遍数组就能解完三、区别你的暴力双层循环固定第 i 个数字只和它后面所有数字 jji配对求和往后找。两层循环重复计算多效率低。哈希字典单层循环走到第 idx 个数字时只去字典查它前面所有数字前面的已经提前存进字典里往前找互补数。只遍历数组一次前面的数据存在字典里快速查询不用重复循环。补充关键优势为什么 “往前找” 更快暴力法每一个数字都要和后面全部数字比对总比对次数 n*(n-1)/2数组越长越卡。哈希法每个数字只做一次减法、一次字典查询查询速度近似瞬间完成全程只走一遍数组。举同一个例子印证逻辑nums[2,7,11,15], target9暴力i0数字 2依次和 j1、j2、j3 相加到 j1 匹配成功。哈希走到 idx1数字 7往前查已存入字典的数字 2直接匹配成功。补充避坑点哈希代码里先判断、再存入就是为了保证永远只查前面的数字绝对不会取到当前自身完美满足题目 “不能使用两次相同元素” 的限制。