Array 与 Hashing¶
Array 和 hash table 是编程中两种最基础的数据结构。本文介绍它们的底层工作原理，然后通过难度递增的问题逐步建立关键的解题模式：双指针、滑动窗口、前缀和以及基于 hash 的查找，并在每一步指出常见陷阱。
-
如果你深刻理解 array 和 hash map，就能解决约 40% 的编程面试题。这两种结构无处不在，因为它们提供了算法最需要的两样东西：快速索引访问（array）和按键快速查找（hash map）。
-
本文教授模式，而非解法。目标是：当你看到一道新题时，能够识别哪种模式适用以及为什么，而不是试图回忆一个记住的解法。
Array¶
-
Array 是一块连续的内存，元素存储在固定的偏移位置。访问元素 \(i\) 的代价是 \(O(1)\)，因为地址就是
base + i * element_size。这是最快的数据访问方式，也是 array 作为默认选择的原因。 -
动态 array（Python 的
list、Java 的ArrayList、C++ 的vector）在满时自动增长。策略是均摊倍增：当 array 满时，分配一个新的双倍大小的 array 并复制所有内容。复制花费 \(O(n)\)，但它发生得很少（每 \(n\) 次插入一次），因此每次插入的均摊代价是 \(O(1)\)。 -
Cache 局部性是 array 在实践中快的原因，而不仅仅是理论上。由于元素连续存储，访问一个元素会将附近的元素加载到 CPU cache（第 13 章）。迭代 array 对 cache 友好；跟随 linked list 中的 pointer 则不然。这种常数因子的差异在实践中可达 10-100 倍。
| 操作 | Array | 动态 Array |
|---|---|---|
| 按索引访问 | \(O(1)\) | \(O(1)\) |
| 追加 | 不支持 | \(O(1)\) 均摊 |
| 在位置 \(i\) 插入 | \(O(n)\) | \(O(n)\) |
| 在位置 \(i\) 删除 | \(O(n)\) | \(O(n)\) |
| 搜索（未排序） | \(O(n)\) | \(O(n)\) |
- 陷阱：在 array 中间插入或删除是 \(O(n)\)，因为所有后续元素都必须移位。如果需要频繁的中间插入，考虑 linked list 或完全不同的方法。
字符串¶
- 字符串是字符的 array。在 Python 中，字符串是不可变的：每次拼接都会创建一个新字符串。在循环中逐字符构建字符串是 \(O(n^2)\)，因为每次拼接都会复制到目前为止的整个字符串。
# 差：O(n^2) 字符串拼接
s = ""
for c in characters:
s += c # 每次复制整个字符串
# 好：O(n) 使用 list 然后 join
parts = []
for c in characters:
parts.append(c)
s = "".join(parts)
-
陷阱：在 Python 的循环中使用
s += c是最常见的性能 bug 之一。始终先收集到 list 中，然后调用.join()。 -
编码：ASCII 使用 7 位（128 个字符）。UTF-8 是可变长度的：ASCII 字符使用 1 字节，带重音符的字符使用 2 字节，汉字/日文字符使用 3 字节，emoji 使用 4 字节。当题目说"小写英文字母"时，字母表大小为 26，这意味着你可以使用固定大小的 array 而非 hash map。
Hash Table¶
-
Hash table 以 \(O(1)\) 的平均情况代价实现按键查找、插入和删除。它通过计算hash function \(h(key)\) 将键转换为 array 索引来工作。
-
Hash function 必须：确定性（相同的键总是产生相同的 hash）、均匀分布（将键均匀分布在各个桶中）、快速计算。
-
碰撞发生在两个不同的键 hash 到同一个索引时。两种主要策略：
-
链地址法（Chaining）：每个桶存储一个键值对的 linked list。发生碰撞时，追加到 list。最坏情况（所有键 hash 到同一个桶）：\(O(n)\)。用好的 hash function 平均情况：\(O(1)\)。
-
开放寻址（Open addressing）：碰撞时，探测下一个空闲槽。线性探测检查下一个槽，然后再下一个，以此类推。对 cache 友好，但会出现聚集（长串的被占用槽）。Robin Hood hashing 通过替换"距离主位置更近"的条目来减少方差。
-
-
负载因子 \(\alpha = n / m\)（元素数/桶数）决定性能。当 \(\alpha\) 超过阈值（通常为 0.75）时，table 重新 hash：分配更大的 table 并重新插入所有元素。代价为 \(O(n)\)，但发生频率很低。
-
Hash map（Python 的
dict，Java 的HashMap）存储键值对。Hash set（Python 的set，Java 的HashSet）只存储键（用于快速成员测试）。
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 查找 | \(O(1)\) | \(O(n)\) |
| 插入 | \(O(1)\) | \(O(n)\) |
| 删除 | \(O(1)\) | \(O(n)\) |
-
Bloom filter 是空间效率高的概率集合。它们能告诉你"肯定不在集合中"或"可能在集合中"（可调的误报率）。使用 \(k\) 个 hash function 和一个位 array。用于数据库（避免对不存在的键进行磁盘读取）、Web cache 和拼写检查器。
-
何时使用 hash map：每当你需要在 \(O(1)\) 内回答"我以前见过这个吗？"或"与这个键关联的计数/索引/值是什么？"时。如果你在反复进行线性扫描寻找某个东西，hash map 几乎肯定能让它更快。
模式：Hash Map 查找¶
- 最基本的模式：使用 hash map 将 \(O(n)\) 扫描替换为 \(O(1)\) 查找。
简单：Two Sum¶
-
问题：给定一个整数 array 和目标值，返回两个数的索引，使其和等于目标值。
-
暴力法 \(O(n^2)\)：检查每对。
-
模式洞察：对于每个数
num，你需要target - num存在于 array 中。与其扫描 array 寻找它，不如将之前见过的数存储在 hash map 中。
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
-
为什么有效：一遍遍历 array。对于每个元素，hash map 查找是 \(O(1)\)。总计：\(O(n)\) 时间，\(O(n)\) 空间。
-
陷阱：不要在检查补数之前将当前数加入 hash map，否则你可能将一个元素与自身匹配。上面代码中的顺序是正确的：先检查，再插入。
中等：Group Anagrams¶
-
问题：给定一个字符串 list，将变位词分组在一起。（"eat"、"tea"、"ate"）是一组。
-
模式洞察：变位词具有相同的字符，只是顺序不同。如果你对每个字符串排序，变位词会产生相同的排序后的键。将该排序后的键用作 hash map 的键。
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # 或使用字符计数 tuple
groups[key].append(s)
return list(groups.values())
- 优化：对每个字符串排序花费 \(O(k \log k)\)，其中 \(k\) 是字符串长度。对于更快的键，计算字符频率并将计数 tuple 用作键：
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)\)。字符计数 tuple 是一种规范形式：对于同一组的所有成员都相同的表示。
-
陷阱：在 Python 中，list 是不可 hash 的（不能作为 dict 的键）。你必须将其转换为 tuple。当人们尝试
groups[count].append(s)时会踩到这个坑。
困难：最长连续序列¶
-
问题：给定一个未排序的 array，找出最长连续序列的长度（例如 [100, 4, 200, 1, 3, 2] → 4，因为 [1, 2, 3, 4]）。
-
暴力法 \(O(n \log n)\)：对 array 排序，然后扫描连续的运行。
-
模式洞察：将所有数字放入 hash set 以实现 \(O(1)\) 查找。对于每个数字，检查它是否是序列的起点（即
num - 1不在 set 中）。如果是，统计序列延伸多远。
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] 会从每个起点扫描整个序列）。
模式：双指针¶
-
双指针模式使用两个索引在 array 中移动，通常从两端向中间或从同一端以不同速度移动。它适用于 array 已排序或需要比较对的情况。
-
何时使用：问题涉及对、子数组或分区，且 array 已排序（或可以排序而不丢失所需信息）。
简单：有效回文¶
-
问题：只考虑字母数字字符并忽略大小写，判断字符串是否是回文。
-
模式：一个指针从开头，一个从末尾。向内移动，比较字符。
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检查。没有它，在像 "!!!" 这样全是非字母数字的字符串上，指针会越界。
中等：Three Sum¶
-
问题：找出 array 中所有和为零的唯一三元组。
-
模式：对 array 排序。固定一个元素，然后对剩余部分使用双指针，找到和为固定元素的相反数的对。
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这一行至关重要。
困难：接雨水¶
-
问题：给定一个高度图（非负整数 array），计算下雨后它能接住多少水。
-
模式洞察：对于每个位置，水位由其左侧最大高度和右侧最大高度的最小值减去当前高度决定。从两端的双指针追踪这些运行中的最大值。
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约束（我们知道右侧有一个更高的 bar，所以右侧不是瓶颈）。我们处理较短的一侧，确保另一侧有更高的 bar。 -
陷阱：许多人尝试先预计算
left_max[i]和right_max[i]array（这可以工作但使用 \(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：该字符可能在当前窗口开始之前就在 map 中了。没有这个检查，你会错误地收缩一个实际上不在当前窗口中的字符。 -
陷阱：使用 set 并从左侧逐个移除字符是正确的，但更慢。hash map 方法直接跳到正确位置。
困难：最小覆盖子串¶
-
问题：给定字符串
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) # (长度, 左, 右)
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_countsdict 与need，这是每步 \(O(|\text{唯一字符}|)\)。have计数器使有效性检查变为 \(O(1)\)。 -
陷阱：检查
window_counts[char] == need[char]（不是>=）确保我们对每个字符恰好递增have一次。如果使用>=，会过度计数。
模式：前缀和¶
- 前缀和 array 存储累积和：
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
# arr[l:r] 的和（包含 l，不含 r）
def range_sum(prefix, l, r):
return prefix[r] - prefix[l]
- 何时使用：问题涉及多个子数组和查询，或找到特定和的子数组。
简单：区间和查询¶
-
问题：给定一个 array，回答多个"从索引 \(l\) 到 \(r\) 的和是多少？"的查询。
-
没有前缀和：每个查询是 \(O(n)\)。有前缀和：\(O(n)\) 预处理，然后每个查询 \(O(1)\)。
中等：和为 K 的子数组¶
-
问题：计算和为 \(k\) 的连续子数组的数量。
-
模式洞察：从索引 \(l\) 到 \(r\) 的子数组和等于
prefix[r+1] - prefix[l]。我们希望这等于 \(k\)，所以prefix[l] = prefix[r+1] - k。对于每个位置，使用 hash map 计算有多少早期前缀和等于current_prefix - k。
def subarray_sum(nums, k):
count = 0
prefix = 0
prefix_counts = {0: 1} # 空前缀和
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
-
这结合了前缀和与 hash map 查找：\(O(n)\) 时间，\(O(n)\) 空间。
-
陷阱：忘记初始化
prefix_counts = {0: 1}。空前缀（任何元素之前）的和为 0。没有这个，你会漏掉从索引 0 开始的子数组。
困难：除自身以外 array 的乘积¶
-
问题：给定一个 array，返回一个 array，其中每个元素是所有其他元素的乘积。不能使用除法。
-
模式：从左侧构建前缀乘积，从右侧构建后缀乘积。每个位置的答案是
left_product * right_product。
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)\) 额外空间（输出 array 不算）。这使用输出 array 本身存储中间前缀乘积，然后在第二次遍历中乘以后缀乘积。
-
陷阱：如果 array 包含零，基于除法的方法会失败。这种前缀/后缀方法能正确处理零，因为它从不执行除法。
常见陷阱汇总¶
| 陷阱 | 示例 | 修复方法 |
|---|---|---|
| 窗口大小差一 | right - left vs right - left + 1 |
画出 2 元素的例子 |
| Python 中的可变默认参数 | def f(seen={}) 在调用间共享状态 |
使用 def f(seen=None) |
| 循环中的字符串拼接 | s += c 在 Python 中是 \(O(n^2)\) |
使用 list.append + "".join" |
在前缀和中忘记 {0: 1} |
漏掉从索引 0 开始的子数组 | 始终用空前缀初始化 |
| 检查前先加入 hash map | Two Sum：在检查补数之前添加 num |
先检查，再插入 |
| 不处理重复 | Three Sum 返回重复三元组 | 跳过连续相等的值 |
| 整数溢出 | C++/Java 中大 array 的和 | 使用 long 或检查边界 |
课后练习（NeetCode）¶
按顺序练习这些题目。每道题都强化本文中的一种模式。
Hash Map 查找¶
- Contains Duplicate — 热身：用 hash set 检查是否见过
- Two Sum — 补数查找
- Group Anagrams — 规范形式作为键
- Top K Frequent Elements — hash map + 桶排序
- Longest Consecutive Sequence — hash set 配合序列起点技巧
- Encode and Decode Strings — 设计序列化方案
双指针¶
- Valid Palindrome — 向内移动的指针
- Two Sum II（已排序） — 在已排序 array 上使用双指针
- Three Sum — 固定 + 双指针 + 去重
- Container With Most Water — 贪心双指针
- Trapping Rain Water — 带运行最大值的双指针
滑动窗口¶
- Best Time to Buy and Sell Stock — 退化窗口
- Longest Substring Without Repeating Characters — 用 hash map 扩展/收缩
- Longest Repeating Character Replacement — 窗口 + 最大频率技巧
- Minimum Window Substring — 扩展直到有效，收缩以最小化
前缀和¶
- Product of Array Except Self — 前缀/后缀乘积