LeeCode热题之哈希表

1、两数之和解法思路读完题目第一个能想到的就是暴力求解for循环嵌套for循环这样虽然能通过但是时间复杂度太大有没有复杂度不是那么大的解法呢有的哈希表需要记住判断某个元素是否存在、统计次数、建立映射关系这些要优先想到哈希。哈希表在Python的实现就是字典和集合查找的平均复杂度只有O(1)而暴力求解一遍是O(n)针对这种映射关系使用字典是可以的。知道使用字典了下一步我们应该怎么想。这是一个数组要把数组中的元素和下标存进字典字典是键值对我们想遍历第一个数组元素查找字典是空字典把它放入空字典然后遍历第二个元素继续查找字典查找和 当前数和为target是字典元素如果找到了直接返回两个元素下标。这个思路看起来可行那就写一下下面这个就是最好的提交结果了看到把下标存成value把元素存为key可能有些人会有疑惑为什么和数组的下标是索引不一样那我们就试着把下标存成key发现查找一次指定元素复杂度是O(n)这样就和暴力求解复杂度一样了。将遍历过的匹配不上的数存入字典能匹配上的直接输出下标因为题目中说只对应一个答案直接返回下标就行。代码实现如下class Solution(object): def twoSum(self, nums, target): hashmap {} for i, num in enumerate(nums): complement target - num if complement in hashmap: return [hashmap[complement], i] hashmap[num] i return []2、字母异位词分组解题思路热题100里面第二个关于哈希的题目是异位词分组先看题目将字母异位词组合在一起就是把所有字符相同的字母放在一起不要求顺序一致这也是一个匹配类的题目如果要复杂度低的话就可以使用哈希。字典键值对可以存放字符串可以把匹配信息当做key匹配到的字符串做value字母的顺序会影响匹配为了统一要将存进的字符串排序再判断是否和字典中key一致一致就存在key对应字典不一致就新建键值对最后转换成列表返回。代码实现如下class Solution(object): def groupAnagrams(self, strs): hashump {} for s in strs: key .join(sorted(s)) if key not in hashump: hashump[key] [] hashump[key].append(s) return list(hashump.values())3、最长连续序列解题思路看到这道题第一个想到的是暴力解法直接排序然后循环遍历这种想法可以解题不符合题目要求的O(n)复杂度想降低复杂度可以尝试用哈希求解。对于这种不需要返回下标的题目用集合就可以。这道题难点在于能不能思考出来怎么判断连续序列的起点和终点如果我们能找到起点只需要循环查询找到终点就得到长度了反之也可以我们找起点就是找连续序列的最小值只要没有比当前数小1的值当前数就是连续序列的最小值查询的时间复杂度是O(1)循环一个集合复杂度是O(n)符合要求接下来就是代码实现先将数组放入集合集合有一个特点就是不重复然后就要记录连续序列长度接着就是依次判断起点和终点然后对比当前最大序列最后遍历结束返回最大序列。代码实现如下class Solution(object): def longestConsecutive(self, nums): num_set set(nums) max_len 0 for x in num_set: if x - 1 not in num_set: current_num x current_len 1 while current_num 1 in num_set: current_len 1 current_num 1 max_len max(current_len,max_len) return max_lenPython新手刷题旨在记录学习情况分享自己的见解如果代码一模一样提交出错可能是缩进和空格混用有问题可以评论留言。