目录

力扣总结 数据结构(四):哈希表

哈希表是针对查询,空间换时间的一种数据结构,一般能够在 O(1) 时间内插入、查询、删除元素, 但不能通过下标访问元素。

哈希表分为哈希集合和哈希映射,哈希集合存储非重复值,哈希映射存储 key 唯一的 (key,value) 对。

python 中一般直接用内置库 set 和 dict 表示哈希集合和哈希映射。 另外还有一些特定用途的内置库,比如 Counter, defaultdict, OrderedDict。

1 基础

1.1 设计

  • 0705 设计哈希集合
  • 0706 设计哈希映射
  • 0535 设计哈希映射 TinyURL 的加密与解密

1.2 哈希集合

  • 0217 存在重复元素
  • 0349 两个数组的交集
  • 0500 键盘行
  • 0575 分糖果

1.3 哈希映射

  • 0001 两数之和
  • 0205 同构字符串
  • 0219 存在重复元素 II
  • 0599 两个列表的最小索引总和

1.4 设计键

  • 0036 有效的数独
  • 0049 字母异位词分组
  • 0318 最大单词长度乘积
  • 0676 实现一个魔法字典

1.5 Counter

  • 0350 两个数组的交集 II
  • 0409 最长回文串
  • 0532 数组中的 k-diff 数对
  • 0594 最长和谐子序列

2 进阶

2.1 设计

  • 0146 LRU 缓存机制
  • 0380 常数时间插入、删除和获取随机元素
  • 0381 O(1) 时间插入、删除和获取随机元素 - 允许重复

2.2 应用

3 挑战

3.1 设计

  • 0432 全 O(1) 的数据结构
  • 0460 LFU 缓存
  • 0710 黑名单中的随机数

3.2 应用

  • 0149 直线上最多的点数
  • 0166 分数到小数
  • 0336 回文对
  • 1178 猜字谜