0 Two Pointers Basic 双指针是什么？ 用两个指针（下标）在数组/链表上协同移动，通过缩小搜索范围来降低复杂度 两大类型： 类型 特征 典型题 对撞指针 一头一尾，向中间逼近 盛水容器、三数之和 快慢指针 同向移动，速度不同 移动零、链表环检测 使用双指针的条件： 通常数组有序（或者问题本身有单调性） 如果无序，往往需要先排序 双指针能降低复杂度原因：利用了单调性，使得指针不需要回退，将 O(n²) 降到 O(n) 1 快慢指针（数组原地操作） 1.1 移动零 | Easy 题目： 将数组中所有 0 移到末尾，保持非零元素的相对顺序。原地操作 [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0] 思路分析： 用快慢指针，left指向当前最左边的0的位置，i找非0，然后swap left：慢指针，始终指向下一个非零元素该放的位置 i： 快指针，遍历数组寻找非零元素 left左边都是已经处理好的非零元素，每找到一个非零元素，就交换到left位置，然后left右移 走一遍[0, 1, 0, 3, 12]: i=0, nums[0]=0 → 是0，跳过 zero=0, [0, 1, 0, 3, 12] i=1, nums[1]=1 → 非0，和zero交换 zero=1, [1, 0, 0, 3, 12] i=2, nums[2]=0 → 是0，跳过 zero=1, [1, 0, 0, 3, 12] i=3, nums[3]=3 → 非0，和zero交换 zero=2, [1, 3, 0, 0, 12] i=4, nums[4]=12 → 非0，和zero交换 zero=3, [1, 3, 12, 0, 0] 踩坑记录：搞清楚两个指针的含义以及交换条件 ...

0 Hash Table Basic 哈希表是什么？ hash table通过hash function将key映射到数组下标，实现O(1)的insert, search, delete 什么时候用哈希表？ 典型信号词：查找，配对，计数，去重 需要“快速查找判断某个元素是否存在”或“快速找到某个元素对应的值” python中哈希表用法：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(ht["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) 重点：可变对象不能作为dict的key，比如list, Counter；tuple/int/str可以 ...