哈希表题解：O(1) 查询背后也有边界

哈希表题解：O(1) 查询背后也有边界

一、哈希表不是无脑加速器

哈希表在算法题里太常见了：两数之和、最长连续序列、字母异位词、前缀和计数。它的优势是平均 O(1) 查询，但这不代表可以无脑使用。哈希表会消耗空间，也会带来 key 设计、重复元素、计数和边界问题。

很多哈希题写错，不是不会用 dict，而是没想清楚存什么。存值、存下标、存次数、存前缀和、存第一次出现位置，含义完全不同。

二、解题链路：先定义 key 和 value

flowchart LR A[题目目标] --> B[需要快速查什么] B --> C[设计 key] C --> D[设计 value] D --> E[处理重复和边界]

哈希表设计的核心问题是：我希望用 O(1) 找到什么？答案清楚，代码就不容易乱。

三、代码示例：前缀和计数

from collections import defaultdict def subarray_sum(nums, k): count = defaultdict(int) count[0] = 1 prefix = ans = 0 for x in nums: prefix += x ans += count[prefix - k] count[prefix] += 1 return ans

这里哈希表存的是“某个前缀和出现了几次”。count[0] = 1是边界，表示从数组开头开始的子数组。这个初始化漏了，很多用例会错。

四、工程边界：空间复杂度也要说清

哈希表通常把时间降下来，但空间会上去。算法题解里要写清空间复杂度 O(n)。如果题目数据很大，空间也可能成为问题。工程里做缓存、去重、索引，也要面对同样的取舍。

取舍方面，哈希表适合快速查找和计数，但不适合需要有序遍历的场景。需要顺序、排名、区间，就可能要用堆、树状数组、平衡树或排序。不要看到 O(1) 就兴奋，先看问题需要什么能力。

还要注意哈希 key 的稳定性。字符串组合 key 要避免冲突，比如a + "#" + b比直接拼接更安全；对象作为 key 时要考虑不可变性。刷题里问题小，工程里 key 设计不严谨会变成线上 bug。

哈希表还有一个常见坑：更新顺序。前缀和题里必须先查询prefix-k，再把当前 prefix 计数加一，否则会把当前元素当成之前的前缀，导致空子数组被算进去。类似地，两数之和里如果同一个元素不能用两次，也要先查再插入，或者插入时处理下标。

计数类问题还要区分 set 和 map。只关心是否出现，用 set；关心出现次数，用 map；关心第一次出现位置，就不能覆盖旧值。数据结构选错，代码表面简洁，答案会悄悄错。

最后，哈希题解要讲清楚最坏情况。理论上哈希可能退化，但面试和刷题通常讨论平均复杂度。写清“平均 O(1)”比直接写“稳定 O(1)”更严谨。

滑动窗口和哈希表也经常组合。比如最长无重复子串，用哈希表记录字符最近位置，左边界只向右移动。这里 value 不是次数，而是下标；如果写成 set，也能做，但需要循环删除。不同 value 设计，会影响代码复杂度。

工程里哈希表还要考虑内存释放。算法题函数结束就释放，服务进程里缓存 map 如果没有上限，会一直长。刷题时培养空间意识，写工程代码时就不容易无脑堆 map。

这个习惯很值钱。

五、总结

哈希表题解的关键，是明确 key 和 value 的含义。O(1) 查询很好，但重复元素、边界初始化、空间复杂度和 key 稳定性都要讲清楚。