两数之和
1、if a in dict:
字典中in操作符的语法是key in dict(而非value.)
可以从“字典中key唯一而value可重复”的角度考虑。
2、enumerate函数
enumerate(iteration, start)
其中iteration为需要遍历的参数,如列表、元组等。start表示开始遍历的值,默认为0。
enumerate的使用及返回值如下例:
for i,x in enumerate(nums): #i从start(默认0)开始遍历,x=nums[i]
3、暴力枚举vs哈希表(时空复杂度分析)
Ⅰ.暴力枚举算法
for i in range(len(nums)): for j in range(i+1,len(nums)):
时间复杂度
空间复杂度,没有再开辟更多内存空间。
Ⅱ.哈希
hashtable = dict() for i, num in enumerate(nums):
时间复杂度
空间复杂度
可见空间与时间不可兼得,使用哈希表算法属于空间换时间。
4、哈希表
哈希表(Hash table),也叫散列表,是一种通过键访问值的数据结构,python中的字典即哈希表的实现。
hashtable = {} #创建一个哈希表 for i, num in enumerate(nums): #一次遍历 if target - num in hashtable: #在哈希表中查找对应的差值,注意为key in dict return [hashtable[target - num], i] hashtable[nums[i]] = i #在哈希表中添加元素,注意将值添加为key,索引添加为value