0 Hash Table basic

  1. 哈希表是什么？

hash table通过hash function将key映射到数组下标，实现O(1)的平均查找/插入/删除，python对应dict & set

  1. 什么时候用哈希表？

典型信号词：查找，配对，计数，去重 需要"快速查找判断某个元素是否存在"或"快速找到某个元素对应的值"

  1. dict & set
 1from collections import defaultdict, Counter
 2
 3# dict
 4ht = {}
 5ht = dict()
 6ht["key"] = "value" # 插入/更新 O(1)
 7ht["name"] = "rhea"
 8value = ht.get("name", "default") # 查找，不存在返回default
 9print("name" in ht) # 判断key是否存在 O(1)
10del ht["key"] # 删除 O(1)
11
12# defaultdict自动初始化
13ht1 = defaultdict(int) # 默认值为0，d[key]不存在时自动为0
14ht2 = defaultdict(list) # 默认值为[]，d[key]不存在时自动创建空list
15
16ht1["a"] += 1 # ht1: {"a": 1}
17print(ht1["b"]) # 0
18
19ht2["group"].append(1) # defaultdict(list, {'group': [1, 1]})
20print(ht2["team"]) # []
21
22# Counter 计数器
23counter = Counter("abracadabra")
24# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
25print(counter["a"]) # 5
26print(counter.most_common(2)) # [('a', 5), ('b', 2)] list
27
28# 常见用法：统计频次
29freq = {}
30for ch in s:
31    freq[ch] = freq.get(ch, 0) + 1
32
33# 等价于
34freq = Counter(s)

1# set
2s = set()
3s.add(x)        # 添加 O(1)
4print(x in s)   # 判断存在 O(1)
5s.discard(x)    # 删除（不报错） O(1)

 1# defaultdict(int)：词频统计
 2freq = defaultdict(int)
 3for word in words:
 4    freq[word] += 1 # 不用判断key是否存在
 5
 6# defaultdict(list)：按首字母分组
 7groups = defaultdict(list)
 8for word in words:
 9    groups[word[0]].append(word)
10
11# defaultdict(list)：建图邻接表
12graph = defaultdict(list)
13for u, v in edges:
14    graph[u].append(v)
15    graph[v].append(u)

Counter 对象不能作为 dict 的 key，因为它是可变对象，不可哈希 同理,list对象也不能作为dict的key，但是tuple可以

1 两数之和（LC 1） Easy

题目： 给定整数数组 nums 和目标值 target，找出和为 target 的两个元素的下标。假设恰好有一个解，同一元素不能用两次

思路分析：

暴力做法：两层for loop，时间复杂度是O($n^2$)

哈希：

  • 对于当前num，我们需要找target - num $\Rightarrow$ 之前遍历过的nums里面是否存在target - num $\Rightarrow$ hash search
  • 一边遍历，一边把已经见过的数存进哈希表，对于每一个新数，先查找哈希表中是否有它
1class Solution:
2    def twoSum(self, nums: List[int], target: int) -> List[int]:
3        seen = {}
4        for idx, num in enumerate(nums):
5            complement = target - num
6            if complement in seen:
7                return [seen[complement], idx]
8            seen[num] = idx

复杂度分析：

  • 时间O(n)
  • 空间O(n)

拓展：

  • 如果数组有序？ → 用双指针更优（空间 O(1)） LC 167
  • 如果要返回所有配对？ → 需要注意去重，用 Counter 更方便
  • 三数之和？ → 排序 + 双指针

2 字母异位词分组（LC 49） Medium

题目： 给定字符串数组，将字母异位词（anagram）分组

  • ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]]

思路分析: 字母异位词的特征是Counter(word)相同，但是counter object不能作为哈希key；特征也可以是word排序后相同 $\Rightarrow$ tuple as key

plan1: 排序作为key

1class Solution:
2    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
3        groups = defaultdict(list)
4        for s in strs:
5            key = tuple(sorted(s))
6            groups[key].append(s)
7        return list(groups.values())

时间复杂度分析：O(n · k·log k)，其中 k 是字符串最大长度

1class Solution:
2    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
3        groups = defaultdict(list)
4        for s in strs:                # 循环n次
5            key = tuple(sorted(s))    # sorted: O(k logk), tuple: O(k)
6            groups[key].append(s)     # 哈希查找：O(k)，append: O(1)
7        return list(groups.values())

plan2: 计数元组作为 key（当 k 很大时更优）

 1class Solution:
 2    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
 3        groups = defaultdict(list)
 4        for s in strs:
 5            counter = [0] * 26
 6            for c in s:
 7                counter[ord(c) - ord('a')] += 1
 8            key = tuple(counter)
 9            groups[key].append(s)
10        return list(groups.values())

时间复杂度分析:

 1class Solution:
 2    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
 3        groups = defaultdict(list)
 4        for s in strs:							# 循环n次
 5            counter = [0] * 26                  # O(26) = O(1)
 6            for c in s:                         # O(k)
 7                counter[ord(c) - ord('a')] += 1 # O(1)
 8            key = tuple(counter)			    # O(26) = O(1)
 9            groups[key].append(s)       # 哈希查找:O(26) = O(1), append: O(1)
10        return list(groups.values())
  • 时间 O(n · k)
  • 空间 O(n · k)
  • 优势: 把 key 的计算从 O(k log k) 降到了 O(k)，因为 26 位数组的操作全是常数级的

拓展：

  • 有效的字母异位词（LC 242）： 判断两个字符串是否为异位词，直接 Counter(s) == Counter(t) 即可
  • 找到字符串中所有字母异位词（LC 438）： 滑动窗口 + 计数比较

3 最长连续序列（LC 128）Medium

题目： 给定未排序的整数数组 nums，找出最长的连续元素序列的长度。要求 O(n)。

  • [100, 4, 200, 1, 3, 2] → 4（序列是 [1, 2, 3, 4]）

思路分析： 排序能pass，但是时间复杂度O(n logn)，不符合O(n)要求 只从序列起点开始计数，判断每个数是否为序列起点：x - 1 not in nums 需要去重set()

 1class Solution:
 2    def longestConsecutive(self, nums: List[int]) -> int:
 3        nums_set = set(nums)                    
 4        best = 0
 5
 6        for num in nums_set:
 7            if num -1 not in nums_set:
 8                length = 1
 9                while num + length in nums_set:
10                    length += 1
11                best = max(best, length)
12            
13        return best

复杂度分析：

  • 时间O(n): 摊还分析（amortized analysis）
    • 看上去有两重循环,但是每个元素最多被 while 访问一次，所有 while 加起来总步数 = n
    • while 循环的关键分析：不是"每个元素触发一次 O(n) 的 while"，而是"所有 while 加起来总共只走 O(n) 步"
if num - 1 not in nums_set 保证了只有连续序列的起点才会进入 while 循环。
比如 [1,2,3,4,100,101]：

	num=1：是起点 → while 走 4 步（1,2,3,4）
	num=2：2-1=1 在 set 中 → 跳过
	num=3：跳过
	num=4：跳过
	num=100：是起点 → while 走 2 步（100,101）
	num=101：跳过
  • 空间O(n): nums_set = set(nums) # O(n)

4 有效的字母异位词（LC 242）Easy

题目：给定两个字符串s和t ，编写一个函数来判断t是否是s的字母异位词

1class Solution:
2    def isAnagram(self, s: str, t: str) -> bool:
3        return Counter(s) == Counter(t)

5 两个数组的交集（LC 349） Easy

题目：给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。 不考虑输出结果的顺序 。

1class Solution:
2    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
3        return list(set(nums1) & set(nums2))

6 和为 K 的子数组（LC 560） Medium

题目：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

暴力做法: 两层循环

 1class Solution:
 2    def subarraySum(self, nums: List[int], k: int) -> int:
 3        n = len(nums)
 4        cnt = 0
 5        for i in range(n):
 6            s = 0
 7            for j in range(i, n):
 8                s += nums[j]
 9                if s == k:
10                    cnt += 1
11        return cnt

前缀和 + 哈希表：O(n)

  • 前缀和：sum[i, …, j] = prefix[j] - prefix[i-1]
  • 想找和为 k 的子数组，即 prefix[j] - prefix[i-1] = k，等价于找之前是否存在 prefix[i-1] = prefix[j] - k，用哈希表 O(1) 查找。
 1class Solution:
 2    def subarraySum(self, nums: List[int], k: int) -> int:
 3        cnt = 0
 4        prefix = 0
 5        seen = defaultdict(int)
 6        seen[0] = 1
 7
 8        for num in nums:
 9            prefix += num
10            cnt += seen[prefix - k]
11            seen[prefix] += 1
12
13        return cnt