数组与哈希表¶
数组和哈希表是编程中最基础的两个数据结构。本篇将讲解它们在底层如何工作，然后通过逐渐深入的问题，构建关键的解题模式：双指针、滑动窗口、前缀和以及基于哈希的查找，并在每一步指出常见陷阱。
-
如果你深入理解数组和哈希映射，就能解决大约 40% 的编程面试题。这两种结构无处不在，因为它们提供了算法最需要的两样东西：快速索引访问（数组）和按键快速查找（哈希映射）。
-
本篇教的是模式，而不是解法。目标是当你遇到一个新问题时，能够识别出适用哪种模式以及为什么，而不是试图回忆起背诵过的答案。
数组¶
-
数组 是一块连续的内存，元素存储在固定的偏移量上。访问第 \(i\) 个元素的时间为 \(O(1)\)，因为地址就是
base + i * element_size。这是最快的数据访问方式，也解释了为什么数组是默认选择。 -
动态数组（Python 的
list，Java 的ArrayList，C++ 的vector）在容量满时会自动扩容。策略是 均摊加倍：当数组满了，分配一个两倍大小的新数组，将所有元素复制过去。复制成本为 \(O(n)\)，但由于发生的频率很低（每 \(n\) 次插入才发生一次），每次插入的均摊成本为 \(O(1)\)。 -
缓存局部性 是数组在实际中更快的原因，而不仅仅是理论。因为元素连续存储，访问一个元素会将附近的元素加载到 CPU 缓存中（参见第 13 章）。遍历数组是缓存友好的，而在链表中逐个跟随指针则不是。这个常数因子的差异在实际中可能达到 10-100 倍。
| 操作 | 静态数组 | 动态数组 |
|---|---|---|
| 按索引访问 | \(O(1)\) | \(O(1)\) |
| 追加 | 不适用 | 均摊 \(O(1)\) |
| 在位置 \(i\) 插入 | \(O(n)\) | \(O(n)\) |
| 删除位置 \(i\) | \(O(n)\) | \(O(n)\) |
| 查找（未排序） | \(O(n)\) | \(O(n)\) |
- 陷阱：在数组中间插入或删除是 \(O(n)\)，因为所有后续元素都需要移动。如果你需要频繁在中间插入，可以考虑链表或完全不同的方法。
字符串¶
- 字符串 是字符的数组。在 Python 中，字符串是不可变的：每次拼接都会创建一个新字符串。在循环中逐个字符构建字符串的时间复杂度为 \(O(n^2)\)，因为每次拼接都会复制整个已有字符串。
# 错误：O(n^2) 的字符串拼接
s = ""
for c in characters:
s += c # 每次都复制整个字符串
# 正确：O(n) 使用列表然后 join
parts = []
for c in characters:
parts.append(c)
s = "".join(parts)
-
陷阱：在 Python 中，循环内的
s += c是最常见的性能错误之一。始终先收集到列表中，然后调用.join()。 -
编码：ASCII 使用 7 位（128 个字符）。UTF-8 是变长编码：ASCII 字符使用 1 字节，带重音字符使用 2 字节，中文/日文字符使用 3 字节，表情符号使用 4 字节。当题目中说“小写英文字母”时，字母表大小为 26，这意味着你可以使用固定大小的数组而不是哈希映射。
哈希表¶
-
哈希表 以平均 \(O(1)\) 的时间复杂度实现键到值的映射，支持查找、插入和删除。它的工作原理是计算一个哈希函数 \(h(key)\)，将键转换为数组索引。
-
哈希函数必须满足：确定性（同一个键总是产生相同的哈希）、均匀性（将键均匀分布到各个桶中）以及计算快速。
-
哈希冲突 发生在两个不同的键哈希到同一个索引时。两种主要策略：
-
链地址法：每个桶存储一个键值对的链表。发生冲突时，追加到链表末尾。最坏情况（所有键都哈希到同一个桶）：\(O(n)\)。在好的哈希函数下平均情况：\(O(1)\)。
-
开放地址法：发生冲突时，探测下一个空槽位。线性探测 检查下一个槽位，再下一个，依此类推。它缓存友好，但会出现聚集（长连续占用槽位）。Robin Hood 哈希 通过将“离家乡更近”的条目位移，来减少方差。
-
-
负载因子 \(\alpha = n / m\)（条目数 / 桶数）决定性能。当 \(\alpha\) 超过阈值（通常为 0.75）时，表会再哈希：分配一个更大的表，并重新插入所有元素。这需要 \(O(n)\) 时间，但发生频率较低。
-
哈希映射（Python 的
dict，Java 的HashMap）存储键值对。哈希集合（Python 的set，Java 的HashSet）只存储键（用于快速成员测试）。
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 查找 | \(O(1)\) | \(O(n)\) |
| 插入 | \(O(1)\) | \(O(n)\) |
| 删除 | \(O(1)\) | \(O(n)\) |
-
布隆过滤器 是一种节省空间的概率性集合。它可以告诉你“肯定不在集合中”或“可能在集合中”（具有可调的假阳性率）。它使用 \(k\) 个哈希函数和一个位数组。用于数据库（避免对不存在的键进行磁盘读取）、Web 缓存和拼写检查器。
-
何时使用哈希映射：当你需要以 \(O(1)\) 时间回答“我以前见过这个吗？”或“与这个键关联的值/计数/索引是什么？”时。如果你在反复进行线性扫描来寻找某个东西，哈希映射几乎肯定能使其更快。
模式：哈希映射查找¶
- 最基本的模式：用哈希映射将 \(O(n)\) 的扫描替换为 \(O(1)\) 的查找。
简单：两数之和¶
-
问题：给定一个整数数组和一个目标值，返回两个数字的索引，使它们的和等于目标值。
-
暴力解法 \(O(n^2)\)：检查每一对。
-
模式洞察：对于每个数字
num，你需要target - num存在于数组中的某处。与其扫描数组去查找，不如将之前见过的数字存储在哈希映射中。
def two_sum(nums, target):
seen = {} # 值 -> 索引
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
-
为什么有效：一次遍历数组。对于每个元素，哈希映射查找是 \(O(1)\)。总复杂度：\(O(n)\) 时间，\(O(n)\) 空间。
-
陷阱：不要在检查补数之前将当前数字加入哈希映射，否则可能会匹配到自身。上面代码的顺序是正确的：先检查，后插入。
中等：字母异位词分组¶
-
问题：给定一个字符串列表，将字母异位词分组在一起。（"eat", "tea", "ate" 为一组）。
-
模式洞察：字母异位词包含相同的字符，只是顺序不同。如果对每个字符串排序，字母异位词会产生相同的排序后键。使用这个排序后的键作为哈希映射的键。
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # 或者使用字符计数元组
groups[key].append(s)
return list(groups.values())
- 优化：对每个字符串排序的成本为 \(O(k \log k)\)，其中 \(k\) 是字符串长度。为了更快的键，可以统计字符频率，并使用计数元组作为键：
def group_anagrams_fast(strs):
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values())
-
这样每个字符串是 \(O(k)\) 而不是 \(O(k \log k)\)。字符计数元组是一种规范形式：对于同一组中的所有成员，该表示是相同的。
-
陷阱：在 Python 中，列表不可哈希（不能作为字典的键）。你必须转换为元组。很多人会尝试
groups[count].append(s)而失败。
困难：最长连续序列¶
-
问题：给定一个未排序的数组，找出最长连续序列的长度（例如 [100, 4, 200, 1, 3, 2] → 4，因为 [1,2,3,4]）。
-
暴力解法 \(O(n \log n)\)：对数组排序，然后扫描连续段。
-
模式洞察：将所有数字放入一个哈希集合，实现 \(O(1)\) 查找。对于每个数字，检查它是否是一个序列的起点（即
num - 1不在集合中）。如果是，则计算该序列能延伸多长。
def longest_consecutive(nums):
num_set = set(nums)
best = 0
for num in num_set:
# 仅从序列的起点开始计数
if num - 1 not in num_set:
length = 1
while num + length in num_set:
length += 1
best = max(best, length)
return best
-
为什么是 \(O(n)\)：内层
while循环在所有迭代中总共最多执行 \(n\) 次（每个数字最多被访问两次：一次在外层循环，一次在while扩展中）。if num - 1 not in num_set的守卫确保了仅从序列起点开始计数。 -
陷阱：如果没有
if num - 1 not in num_set的检查，你会从每个元素开始计数，最坏情况下变成 \(O(n^2)\)（例如 [1,2,3,…,n] 会从每个起点扫描整个序列）。
模式：双指针¶
-
双指针 模式使用两个索引在数组中移动，通常是从两端向中间移动，或者从同一端以不同速度移动。当数组已排序，或者需要比较元素对时，这个模式有效。
-
何时使用：问题涉及元素对、子数组或分区，并且数组已排序（或者可以在不丢失必要信息的情况下排序）。
简单：验证回文串¶
-
问题：判断一个字符串是否是回文串，只考虑字母数字字符并忽略大小写。
-
模式：一个指针在开头，一个在结尾。将它们向内移动，比较字符。
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# 跳过非字母数字字符
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
- 陷阱：忘记内层 while 循环中的
left < right条件。如果没有它，对于像 "!!!"（全是非字母数字）这样的字符串，指针可能会越界。
中等：三数之和¶
-
问题：找出数组中所有和为 0 且不重复的三元组。
-
模式：对数组排序。固定一个元素，然后对剩余部分使用双指针找到和为固定元素相反数的两个数。
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
# 跳过重复的固定元素
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
target = -nums[i]
while left < right:
total = nums[left] + nums[right]
if total < target:
left += 1
elif total > target:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
# 跳过重复
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return result
-
为什么有效：排序为 \(O(n \log n)\)。每个固定元素的双指针扫描是 \(O(n)\)。总复杂度：\(O(n^2)\)，这是该问题的最优复杂度（你必须考虑所有对）。
-
陷阱：处理重复是最难的部分。如果没有跳过重复的逻辑（包括固定元素和双指针结果），你会返回重复的三元组。
if i > 0 and nums[i] == nums[i-1]: continue这一行至关重要。
困难：接雨水¶
-
问题：给定一个高程图（非负整数数组），计算下雨后能接住多少水。
-
模式洞察：对于每个位置，水位由左侧最大高度和右侧最大高度的最小值减去当前高度决定。双指针从两端向中间移动，跟踪这些滚动最大值。
def trap(height):
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
-
为什么有效：关键洞察是如果
height[left] < height[right]，那么left位置的水位由left_max决定（我们知道右边有更高的柱子，所以右侧不会成为瓶颈）。我们处理较矮的一侧，保证另一侧有更高的柱子。 -
陷阱：许多人尝试先预计算
left_max[i]和right_max[i]数组（这可行但使用 \(O(n)\) 空间）。双指针方法实现了 \(O(1)\) 空间。此外，在最大值更新中混淆>=与>会导致水的计算差一。
模式：滑动窗口¶
-
滑动窗口 模式维护一个窗口（连续子数组），在遍历过程中扩展和收缩。它适用于询问满足某种条件的子数组或子字符串的问题。
-
何时使用：问题要求满足约束的最长/最短子数组或子字符串，并且窗口的扩展/收缩是单调的（添加元素只能使约束更难或更容易满足，而不会同时具有两种效果）。
-
模板：
def sliding_window(arr):
left = 0
state = ... # 窗口状态（计数、和等）
best = ...
for right in range(len(arr)):
# 扩展：将 arr[right] 加入窗口状态
update_state(state, arr[right])
# 收缩：当约束被违反时，从左端收缩
while constraint_violated(state):
remove_from_state(state, arr[left])
left += 1
# 更新答案
best = max(best, right - left + 1) # 或者 min，视问题而定
return best
简单：买卖股票的最佳时机¶
-
问题：给定每日股价，计算一次买入和一次卖出（买入在卖出之前）的最大利润。
-
模式：跟踪迄今为止见过的最低价格（窗口的左边界），并在每一天计算利润。
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
- 这是滑动窗口的退化形式：左指针（最低价格）仅在遇到新的最小值时向前移动。\(O(n)\) 时间，\(O(1)\) 空间。
中等：无重复字符的最长子串¶
-
问题：找出不包含重复字符的最长子串的长度。
-
模式：通过移动
right扩展窗口。当发现重复字符时，从左端收缩窗口直到重复字符被移除。
def length_of_longest_substring(s):
char_index = {} # 字符 -> 它最近出现的索引
left = 0
best = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1 # 跳到重复字符的下一个位置
char_index[char] = right
best = max(best, right - left + 1)
return best
-
为什么需要
char_index[char] >= left：该字符可能在当前窗口开始之前就已经在映射中了。如果没有这个检查，你会错误地为一个实际上不在当前窗口中的字符收缩窗口。 -
陷阱：使用集合并逐个从左移除字符是正确的，但较慢。哈希映射方法直接跳到正确的位置。
困难：最小覆盖子串¶
-
问题：给定字符串
s和t，在s中找到包含t中所有字符的最小子串。 -
模式：扩展窗口直到包含所有需要的字符，然后从左端收缩以找到最小的有效窗口。
from collections import Counter
def min_window(s, t):
if not t or not s:
return ""
need = Counter(t) # 我们需要的字符及其计数
have = 0 # 我们已经满足数量要求的独特字符数
required = len(need) # 需要满足的独特字符数
left = 0
best = (float('inf'), 0, 0) # (长度, left, right)
window_counts = {}
for right in range(len(s)):
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
# 检查该字符的计数是否达到了要求
if char in need and window_counts[char] == need[char]:
have += 1
# 当窗口有效时，从左端收缩
while have == required:
# 更新最佳结果
if (right - left + 1) < best[0]:
best = (right - left + 1, left, right)
# 移除最左边的字符
left_char = s[left]
window_counts[left_char] -= 1
if left_char in need and window_counts[left_char] < need[left_char]:
have -= 1
left += 1
length, start, end = best
return s[start:end + 1] if length != float('inf') else ""
-
陷阱：
have计数器是关键优化。没有它，你需要每一步都比较整个window_counts字典与need，那是 \(O(|\text{unique chars}|)\) 每步。have计数器使有效性检查变为 \(O(1)\)。 -
陷阱：检查
window_counts[char] == need[char]（而不是>=）确保每个字符只增加一次have。如果使用>=，会重复计数。
模式：前缀和¶
- 前缀和 数组存储累计和：
prefix[i] = sum(arr[0:i])。一旦以 \(O(n)\) 时间构建好，任何子数组的和都可以在 \(O(1)\) 时间内计算：sum(arr[l:r]) = prefix[r] - prefix[l]。
def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i + 1] = prefix[i] + arr[i]
return prefix
# sum of arr[l:r] (l 包含, r 不包含)
def range_sum(prefix, l, r):
return prefix[r] - prefix[l]
- 何时使用：问题涉及多个子数组求和查询，或者需要找到具有特定和的子数组。
简单：区域和检索¶
-
问题：给定一个数组，回答多个查询“从索引 \(l\) 到 \(r\) 的和是多少？”
-
没有前缀和时：每个查询 \(O(n)\)。有前缀和时：\(O(n)\) 预处理，然后每个查询 \(O(1)\)。
中等：和为 K 的子数组¶
-
问题：统计和为 \(k\) 的连续子数组的个数。
-
模式洞察：从 \(l\) 到 \(r\) 的子数组和等于
prefix[r+1] - prefix[l]。令其等于 \(k\)，则prefix[l] = prefix[r+1] - k。对于每个位置，用哈希映射统计有多少个之前的前缀和等于当前前缀和 - k。
def subarray_sum(nums, k):
count = 0
prefix = 0
prefix_counts = {0: 1} # 空前缀和为 0
for num in nums:
prefix += num
# 有多少个之前的前缀和等于 prefix - k?
count += prefix_counts.get(prefix - k, 0)
prefix_counts[prefix] = prefix_counts.get(prefix, 0) + 1
return count
-
这结合了前缀和与哈希映射查找：\(O(n)\) 时间，\(O(n)\) 空间。
-
陷阱：忘记初始化
prefix_counts = {0: 1}。空前缀（在第一个元素之前）的和为 0。没有它，你会遗漏从索引 0 开始的子数组。
困难：除自身以外数组的乘积¶
-
问题：给定一个数组，返回一个数组，其中每个元素是除自身以外所有元素的乘积。不能使用除法。
-
模式：从左构建前缀乘积，从右构建后缀乘积。每个位置的答案是
左侧乘积 * 右侧乘积。
def product_except_self(nums):
n = len(nums)
result = [1] * n
# 左遍历：result[i] = nums[0..i-1] 的乘积
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# 右遍历：乘上 nums[i+1..n-1] 的乘积
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
-
\(O(n)\) 时间，\(O(1)\) 额外空间（输出数组不计入）。这里使用输出数组本身来存储中间的前缀乘积，然后在第二遍乘入后缀乘积。
-
陷阱：如果数组中包含零，基于除法的方法会失败。这种前缀/后缀方法正确处理零，因为它从不进行除法。
常见陷阱总结¶
| 陷阱 | 示例 | 解决方法 |
|---|---|---|
| 窗口大小的差一错误 | right - left 与 right - left + 1 |
画出两个元素的例子 |
| Python 中的可变默认参数 | def f(seen={}) 在调用间共享状态 |
使用 def f(seen=None) |
| 循环中的字符串拼接 | s += c 在 Python 中是 \(O(n^2)\) |
使用 list.append + "".join |
忘记前缀和中的 {0: 1} |
遗漏从索引 0 开始的子数组 | 始终初始化为空前缀 |
| 检查之前先加入哈希映射 | 两数之和中先加入 num 再检查补数 |
先检查，后插入 |
| 未处理重复 | 三数之和返回重复的三元组 | 跳过连续相等的值 |
| 整数溢出 | C++/Java 中求大数组和 | 使用 long 或检查边界 |
课后练习（NeetCode）¶
按顺序练习。每个练习都巩固本篇中的一个模式。
哈希映射查找¶
- 包含重复 — 热身：用哈希集合记录是否见过
- 两数之和 — 补数查找
- 字母异位词分组 — 规范形式作为键
- 前 K 个高频元素 — 哈希映射 + 桶排序
- 最长连续序列 — 哈希集合 + 起点技巧
- 字符串编码与解码 — 设计序列化方案
双指针¶
- 验证回文串 — 内向指针
- 两数之和 II（已排序） — 已排序数组上的双指针
- 三数之和 — 固定 + 双指针 + 去重
- 盛最多水的容器 — 贪心双指针
- 接雨水 — 带滚动最大值的双指针
滑动窗口¶
- 买卖股票的最佳时机 — 退化窗口
- 无重复字符的最长子串 — 用哈希映射扩展/收缩
- 替换后最长重复字符 — 窗口 + 最大频率技巧
- 最小覆盖子串 — 扩展到有效，收缩以最小化
前缀和¶
- 除自身以外数组的乘积 — 前缀/后缀乘积