哈希表

d = {"apple": 3, "banana": 5}
d["cherry"] = 7           # 增
d["apple"] = 10           # 改（覆盖旧值）
val = d.get("grape", 0)   # 查，不存在返回默认值
del d["banana"]           # 删
val = d.pop("cherry", None)
if "apple" in d:          # 判断键是否存在
    print(d["apple"])

for k, v in d.items():    # 遍历键值对；也可用 .keys()、.values()
    print(k, v)

squared = {x: x ** 2 for x in [1, 2, 3, 4]}
# {1: 1, 2: 4, 3: 9, 4: 16}

from collections import Counter

cnt = Counter(["apple", "banana", "apple", "cherry", "banana", "apple"])
# Counter({'apple': 3, 'banana': 2, 'cherry': 1})

cnt["grape"]               # 不存在返回 0，不抛异常
cnt.most_common(2)         # [('apple', 3), ('banana', 2)]

freq = Counter("abracadabra")  # 字符频率统计
# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

from collections import defaultdict

# defaultdict(int)：默认值 0，适合计数
counter = defaultdict(int)
for ch in "hello":
    counter[ch] += 1  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

# defaultdict(list)：默认值空列表，适合分组
groups = defaultdict(list)
for category, item in [("fruit", "apple"), ("fruit", "banana"), ("veggie", "carrot")]:
    groups[category].append(item)

# defaultdict(set)：去重分组，常用于建图
graph = defaultdict(set)
for u, v in [(1, 2), (1, 3), (2, 3)]:
    graph[u].add(v)
    graph[v].add(u)

s = set([1, 2, 2, 3])     # 自动去重 -> {1, 2, 3}
s.add(4)
s.discard(2)               # 不存在也不报错
if 3 in s:                 # O(1) 成员检查
    print("found")

a, b = {1, 2, 3, 4}, {3, 4, 5, 6}
a & b   # 交集 {3, 4}
a | b   # 并集 {1, 2, 3, 4, 5, 6}
a - b   # 差集 {1, 2}
a ^ b   # 对称差集 {1, 2, 5, 6}

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # val -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))
        groups[key].append(s)
    return list(groups.values())

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    prefix_sum = 0
    prefix_count = defaultdict(int)
    prefix_count[0] = 1  # 空前缀
    for num in nums:
        prefix_sum += num
        count += prefix_count[prefix_sum - k]
        prefix_count[prefix_sum] += 1
    return count

def find_anagrams(s: str, p: str) -> list[int]:
    if len(s) < len(p):
        return []
    p_count = Counter(p)
    s_count = Counter(s[:len(p)])
    result = []
    if s_count == p_count:
        result.append(0)
    for i in range(len(p), len(s)):
        # 右端加入
        s_count[s[i]] += 1
        # 左端移出
        left = s[i - len(p)]
        s_count[left] -= 1
        if s_count[left] == 0:
            del s_count[left]
        if s_count == p_count:
            result.append(i - len(p) + 1)
    return result