LeetCode 热题 100 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
悲壮的R4-零基础入门篇终于在短暂的休息后告别了，
即将迎来的是重磅重温默写复写思路篇。
R5-哈希篇
一个月了，还是用回了老算法
经典两层遍历
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:n=len(nums)for i in range(n):for j in range(n):if i!=j and nums[i]+nums[j]==target:return [i,j]return [] 
我得专注于思考一些优化的方法以及优化的原理了，而不是仅仅在于解决问题。
需要用到哈希表。
由于哈希表查找为O(1)复杂度，简化两层循环在于找到i和j之间的关联，关联点在于target是和
所以我们可以遍历一层哈希表，key是值，value是下标。
原理相当于将第二层循环简化成查找是否有key2=target-key1
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:n=len(nums)dict=defaultdict(int)#记录下标for i in range(n):dict[nums[i]]=i#遍历for i in dict.keys():j=target-iif i!=j and j in dict.keys():return [dict[i],dict[j]]#查找不到return []有问题
在第一次遍历记录的时候，如果数组存在相等的两个数，就只会记录最后一个数的下标，这显然不是我们想要的。
所以我们调整，根据下标记录值，保证了不可重复性。
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:n=len(nums)dict=defaultdict(int)#记录下标for i in range(n):dict[i]=nums[i]#遍历for i in dict.keys():for j in dict.keys():if i!=j and dict[i]+dict[j]==target:return [i,j]#查找不到return []这个版本没有优化成功
优化方法：
不用事先去记录哈希表初始化
在遍历数组的同时，查找target-num1是否在哈希表中即可。
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:dict=defaultdict(int)#记录下标for i,num in enumerate(nums):num2=target-numif num2 in dict:return [dict[num2],i]dict[num]=ireturn []
之所以不会出现上面的案例不通过的情况是，他没有初始化哈希表，所以避免了两个相同值记录下标的问题，由于题目给出对于每个输入只能有一个答案，所以不会出现3个相同的值。