力扣100题---哈希

1.两数之和

• 描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

  你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

  你可以按任意顺序返回答案

思路一：

• 暴力模拟，两个变量从前往后遍历，避免重复和自己和自己配对
• 代码：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums) # 获取数组长度
        for i in range(n):
            for j in range(i+1, n):
                if(nums[i] + nums[j] == target):
                    return [i,j]
        
        return []

思路二：

• 使用HASH表记录之前出现过的数字以及它的下标，那么只需要遍历数组一次，即O(N)的复杂度就可以找到对应的答案了
• 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict() # 用字典初始化哈希表
        for i, num in enumerate(nums): # enumerate来获取nums的元素
            if target - num in hashtable: # in来判断是否存在于哈希表
                return[hashtable[target - num], i]
            hashtable[num] = i # 存进哈希表
        return []

2.字母异位词分组

• 描述：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

  字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

思路一：

• 将每个单词的排序后的词作为哈希表的key，依次加入到对应的哈希值里，哈希表的value采取default的list，最终以list的形式返回哈希表的所有值
• 代码：

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list) # 初始化有默认值的哈希表
        for st in strs:
            key = "".join(sorted(st)) # 对st进行排序后再重新连接成一个新的字符串
            mp[key].append(st) # append加入对应的key的哈希值
        return list(mp.values()) #返回list形式的所有哈希值

思路二：

• 把每个单词里26个字母按顺序出现的次数作为哈希表的key
• 代码：

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list) # 初始化哈希表
        for st in strs:
            count = [0] * 26 # 初始化字母出现次数
            for ch in st:
                count[ord(ch) - ord("a")] += 1 # ord获取字母的ASCII码
            mp[tuple(count)].append(st) # list不能直接作为键，先转化为tuple类型
        
        return list(mp.values())

3.最长连续序列

• 描述：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

  请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路一：

• 先对nums去重，存储在set里，本身就是个哈希表，查找速度为O（1）。为了避免重复遍历连续数组，在遍历前先判断当前数字num的num-1是否存在，使得每次遍历都是从连续数据的第一个数开始的。最终整体的时间复杂度为O(N)
• 代码：

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
        num_set = set(nums) # set去重查找迅速

        for num in num_set:
            if num - 1 not in num_set: # 判断是否是连续数组的第一个
                len = 1
                cur_num = num

                while cur_num + 1 in num_set:
                    len += 1
                    cur_num += 1
                
                longest = max(longest, len)
        
        return longest

思路二：

• 利用并查集，把连续数字作为并查集的定义，不断进行合并，那么最终长度最大的并查集就是最长的连续数组。时间复杂度可以看作是O（N）。
• 代码：

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums) #去重
        ans = 0

        fa = {num: num for num in nums}
        size = {num: 1 for num in nums} # 初始化 

        def find(x):
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]
        
        def merge(f, to):  #并查集模板
            f = find(f)
            to = find(to)
            if f != to:
                fa[f] = to
                size[to] += size[f]
        
        for num in nums:
            if num + 1 in nums:
                merge(num, num + 1)
        
        if size: # 防止这是一个空数组
            ans =  max(size.values())
        return ans
        

小节：

• 哈希表的主要作用是降低查找的时间复杂度，从而降低整体的时间复杂度
• 哈希表的初始化
  • dict()
  • collections.defaultdict()—需要默认值
  • set()—初始化为set数据结构，去重的同时查找速度也很快
• 哈希表的键必须是不可变的，包括整数（int）、浮点数（float）、字符串（str）、元组（tuple）。列表（list）是可变的对象，需要转化为tuple再作为哈希表的键