企业官网建设流程全解析

数组与哈希：maths-cs-ai-compendium 教你用四大核心模式破解约 40% 的算法面试题

【免费下载链接】maths-cs-ai-compendiumBecome a cracked AI/ML researcher/engineer with this unconventional textbook covering maths, computing, and ML with intuition.项目地址: https://gitcode.com/GitHub_Trending/mat/maths-cs-ai-compendium

导读：本文是 maths-cs-ai-compendium 第 14 章「数据结构与算法」的第一篇实战指南，聚焦程序员日常与算法面试中出现频率最高的两类数据结构——数组与哈希表。文章先讲透两者"under the hood"的底层原理（内存布局、缓存友好性、哈希碰撞与负载因子），再沿着 Hash Map 查找、双指针、滑动窗口、前缀和四大核心模式，用 Easy→Medium→Hard 的递进题目串起完整解法、复杂度分析与常见陷阱。读完你将掌握"识别模式而非背诵解法"的解题方法论，并能据此独立拆解新问题。

为什么数组和哈希表能覆盖约 40% 的面试题

算法问题本质上需要两种能力：快速的索引访问（数组提供）和快速的按键查找（哈希表提供）。这两类结构恰好是算法需要的两个最基础的能力模块，因此几乎无处不在——无论是 LeetCode/NeetCode 上的经典题，还是日常工程中的去重、计数、缓存、索引设计。

• 深入理解数组与哈希表后，你可以解决约40%的编码面试问题；
• 本文教学目标是模式而非答案：当你在考场上遇到新题时，能识别出它属于哪种模式、为什么适用，而不是回忆一个背过的解法。

这种"模式优先"的思路也正是本章的立论基础：在 00. foundations.md 中明确指出，LeetCode 等平台上有数千道题，但核心模式只有约 15-20 种，面试考察的正是"剥离上下文、识别底层模式"的能力。请先确保你已掌握 Big O 符号（该文件中有完整的复杂度增长层级表与 $n=10^6$ 量级的直观对照），因为本文所有复杂度结论都建立在它之上。

数组：连续内存与 O(1) 随机访问

底层原理：base + i * element_size

数组是一块连续的内存，元素以固定偏移存放。访问第 $i$ 个元素的地址就是简单的base + i * element_size，因此访问代价恒为 $O(1)$——这是理论上的最快数据访问方式，也是数组成为默认选择的原因。

从本仓库的 C++ 视角可以更直观地看到这一点：chapter 16 - SIMD and GPU programming/00. why C++ and how ML frameworks work.md 中float weights[1024];即"1024 个 float 在内存中连续排布"，而std::vector<float>（动态数组）同样保证元素连续存放，这正是它可以被 SIMD 向量单元批量加载的前提。

动态数组：均摊 O(1) 的扩容

Python 的list、Java 的ArrayList、C++ 的std::vector都是动态数组：容量满时自动增长。其策略是均摊加倍（amortised doubling）——数组满时分配两倍大小的新数组并整体拷贝。单次拷贝代价 $O(n)$，但每 $n$ 次插入才发生一次，因此每次插入的均摊代价为 $O(1)$。

缓存局部性：实践中比理论更重要

数组快不只是理论结论，更关键的实践因素是缓存局部性（cache locality）。因为元素连续存放，访问一个元素会顺带把邻近元素加载进 CPU 缓存；顺序遍历数组是"缓存友好"的，而沿着链表指针跳跃则不是。这种常数因子的差距在现实中可达10-100 倍。

本仓库在 chapter 13 - computing and OS/02. computer architecture.md 给出了完整的硬件证据：L1 缓存约 1ns（32-64 KB/核）、L2 约 4ns、L3 约 10ns，而寄存器与 RAM 的速度差约 300 倍；内存层级正是靠时间局部性（反复访问同一数据）与空间局部性（访问邻近数据）来弥合这一差距。数组的顺序访问完美命中空间局部性，因此在 GPU 与 CPU 的矩阵运算、张量加载中，连续内存布局都是性能基石。

操作复杂度一览

陷阱：在数组中间插入或删除是 $O(n)$，因为后续所有元素都要平移。若需要频繁的中间插入，考虑链表或换一种思路（链表在 02. linked lists, stacks, and queues.md 中有完整对比：链表插入 $O(1)$ 但无随机访问、缓存不友好）。

字符串：披着文本外衣的字符数组

字符串就是字符数组。Python 中字符串不可变：每次拼接都会创建新字符串。若在循环里逐字符+=，每步都要拷贝"到目前为止的整个字符串"，总代价是 $O(n^2)$。

# BAD: O(n^2) string concatenation s = "" for c in characters: s += c # copies entire string each time # GOOD: O(n) using a list then 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，意味着你可以用定长数组代替哈希表（这正是后续 Group Anagrams 优化版的核心技巧）。

哈希表：O(1) 按键查找的魔法

原理与哈希函数三要素

哈希表以 $O(1)$ 的平均复杂度完成按键查找、插入与删除。它通过哈希函数$h(key)$ 把键映射为数组下标。一个好的哈希函数必须满足：

• 确定性（deterministic）：同一个键永远得到同一个哈希值；
• 均匀性（uniform）：把键均匀分布到各个桶，避免堆积；
• 快速（fast）：计算开销要小。

碰撞处理：链地址法与开放寻址

当两个不同的键哈希到同一下标时发生碰撞（collision），两种主流策略：

• 链地址法（chaining）：每个桶存一个键值对链表，碰撞时追加到链表尾。最坏情况（所有键落入同一桶）退化为 $O(n)$；好哈希函数下的平均情况是 $O(1)$。
• 开放寻址法（open addressing）：碰撞时探测下一个空槽。**线性探测（linear probing）依次检查下一个槽位，缓存友好，但会因聚集（clustering）**产生连续占用块；Robin Hood hashing通过把"离家更近"的条目换走，降低探测次数的方差。

负载因子与再哈希

负载因子$\alpha = n / m$（元素数/桶数）决定性能。当 $\alpha$ 超过阈值（通常0.75）时触发再哈希（rehash）：分配更大的表并把所有元素重新插入。单次代价 $O(n)$，但发生频率低，均摊后依然高效。

映射 vs 集合：dict vs set

• 哈希映射（Pythondict、JavaHashMap）存键值对；
• 哈希集合（Pythonset、JavaHashSet）只存键，专用于快速成员判断。

布隆过滤器：概率型集合

Bloom filter是节省空间的概率型集合：它能回答"肯定不在集合中"或"可能在集合中"（误判率可调）。它使用 $k$ 个哈希函数和一段位数组。常见应用：数据库避免对不存在的键发起磁盘读、Web 缓存、拼写检查器。

什么时候该上哈希表

每当你要回答"我是否见过这个？"或"与这个键关联的计数/下标/值是多少？"且需要 $O(1)$ 完成时，就上哈希表。如果你发现自己反复做线性扫描找东西，哈希表几乎总能让它更快。

一个来自本仓库的直观佐证：在 chapter 06 - machine learning/03. deep learning.md 中，嵌入层（embedding layer）本质上就是一张查找表——矩阵 $E$ 形状为（词表大小，嵌入维度），查 token $i$ 就是取第 $i$ 行，等价于与 one-hot 向量相乘。这说明"键→值"的 O(1) 查找思想已经渗透到现代深度学习的最底层组件里。

模式一：Hash Map 查找（把 O(n) 扫描换成 O(1) 查询）

最基本的模式：用哈希表把 O(n) 的线性扫描替换为 O(1) 的按键查询。

Easy：Two Sum

问题：给定整数数组和目标值，返回两数之和等于目标值的两个下标。

• 暴力$O(n^2)$：检查每一对。
• 模式洞察：对每个数num，需要"target - num是否存在于数组某处"。与其扫描数组，不如把已见过的数存入哈希表。

def two_sum(nums, target): seen = {} # value -> index 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)$ 空间。

陷阱：不能在检查 complement 之前把当前数加入哈希表，否则可能和自己匹配。上面代码的顺序（先查后插）才是对的。

Medium：Group Anagrams（字谜分组）

问题：给定字符串列表，把互为字谜的字符串分到同一组（如"eat"、"tea"、"ate"一组）。

模式洞察：字谜只是相同字符的不同排列。把每个字符串排序后，字谜会得到相同的排序键，用该排序键作哈希键即可。

from collections import defaultdict def group_anagrams(strs): groups = defaultdict(list) for s in strs: key = tuple(sorted(s)) # or use character count tuple 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)$。这里的字符计数元组就是规范形式（canonical form）：同一组所有成员共享的等价表示。

陷阱：Python 中 list 不可哈希（不能作 dict 键），必须转成 tuple。很多人写groups[count].append(s)时在这里翻车。

Hard：Longest Consecutive Sequence（最长连续序列）

问题：给定无序数组，求最长连续序列的长度（如[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: # only start counting from the beginning of a sequence 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]会从每个起点扫描整段序列）。

模式二：双指针（Two Pointers）

双指针模式用两个下标在数组中移动，通常从两端相向而行，或从同端以不同速度前进。适用于数组已排序、或需要比较配对/划分的场景。

何时使用：问题涉及配对、子数组或划分，且数组已排序（或排序不丢失必要信息）。

Easy：Valid Palindrome（有效回文）

问题：判断字符串是否为回文，只看字母数字字符并忽略大小写。

模式：一个指针在头、一个在尾，向内移动并逐字符比较。

def is_palindrome(s): left, right = 0, len(s) - 1 while left < right: # skip non-alphanumeric characters 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检查，遇到"!!!"（全非字母数字）这类字符串时指针会越界。

Medium：Three Sum（三数之和）

问题：找出数组中所有和为 0 的不重复三元组。

模式：排序数组，固定一个元素，再对剩余部分用双指针找"和为固定元素相反数"的数对。

def three_sum(nums): nums.sort() result = [] for i in range(len(nums) - 2): # skip duplicate fixed elements 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]]) # skip duplicates 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这一行至关重要。

Hard：Trapping Rain Water（接雨水）

问题：给定海拔图（非负整数数组），计算下雨后能接多少水。

模式洞察：每个位置的蓄水量由"左侧最大高度"与"右侧最大高度"中的较小者减去当前高度决定。双指针从两端出发，动态维护这两个运行最大值。

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)$。另外，最大值更新时混淆>=与>会造成蓄水量的 off-by-one 错误。

模式三：滑动窗口（Sliding Window）

滑动窗口模式维护一个连续子数组窗口，随遍历扩张与收缩，适用于"满足某条件的子数组/子串"类问题。

何时使用：问题求满足约束的最长/最短子数组或子串，且窗口的扩张/收缩是单调的（加元素只会使约束变难或变易，不会两者交替）。

通用模板

def sliding_window(arr): left = 0 state = ... # window state (counts, sum, etc.) best = ... for right in range(len(arr)): # expand: add arr[right] to the window state update_state(state, arr[right]) # contract: shrink from the left while constraint is violated while constraint_violated(state): remove_from_state(state, arr[left]) left += 1 # update answer best = max(best, right - left + 1) # or min, depending on problem return best

Easy：Best Time to Buy and Sell Stock（买卖股票的最佳时机）

问题：给定每日价格，求单次买入卖出（先买后卖）的最大利润。

模式：维护"迄今为止的最低价格"（窗口左边界），每天计算当前利润。

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)$ 空间。

Medium：Longest Substring Without Repeating Characters（无重复字符的最长子串）

问题：求不含重复字符的最长子串长度。

模式：右指针扩张窗口；发现重复字符时，从左收缩直到重复被清除。

def length_of_longest_substring(s): char_index = {} # character -> its most recent 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 # jump past the duplicate char_index[char] = right best = max(best, right - left + 1) return best

为什么需要char_index[char] >= left：该字符可能是在当前窗口开始之前就存入 map 的。没有这个检查，你会为一个实际不在当前窗口内的字符错误地收缩窗口。

陷阱：用 set 从左一个字符一个字符移除也可以但更慢；哈希表版本直接跳到正确位置。

Hard：Minimum Window Substring（最小覆盖子串）

问题：给定字符串s和t，求s中包含t全部字符的最小子串。

模式：扩张窗口直到包含全部所需字符，再从左侧收缩以找到最小合法窗口。

from collections import Counter def min_window(s, t): if not t or not s: return "" need = Counter(t) # characters we need and their counts have = 0 # how many unique characters we have in sufficient quantity required = len(need) # how many unique characters we need left = 0 best = (float('inf'), 0, 0) # (length, left, right) window_counts = {} for right in range(len(s)): char = s[right] window_counts[char] = window_counts.get(char, 0) + 1 # check if this character's count now meets the requirement if char in need and window_counts[char] == need[char]: have += 1 # contract from the left while the window is valid while have == required: # update best if (right - left + 1) < best[0]: best = (right - left + 1, left, right) # remove leftmost character 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}|)$；有了它，合法性检查变为 $O(1)$。

陷阱二：必须用window_counts[char] == need[char]（而非>=）判断，才能保证每个字符只把have加一次；用>=会重复计数。

模式四：前缀和（Prefix Sums）

前缀和数组存储累计和：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] (inclusive l, exclusive r) def range_sum(prefix, l, r): return prefix[r] - prefix[l]

何时使用：问题涉及多次子数组和查询，或要找特定和的子数组。

Easy：Range Sum Query（区域和检索）

问题：给定数组，回答多次"下标 $l$ 到 $r$ 的和"查询。

不用前缀和：每次查询 $O(n)$。用前缀和：$O(n)$ 预处理，之后每次查询 $O(1)$。

Medium：Subarray Sum Equals K（和为 K 的子数组）

问题：统计和为 $k$ 的连续子数组个数。

模式洞察：从 $l$ 到 $r$ 的子数组和等于prefix[r+1] - prefix[l]。令它等于 $k$，即prefix[l] = prefix[r+1] - k。对每个位置，用哈希表统计"此前有多少个前缀和等于current_prefix - k"。

def subarray_sum(nums, k): count = 0 prefix = 0 prefix_counts = {0: 1} # empty prefix sum for num in nums: prefix += num # how many earlier prefix sums equal 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 开始的子数组。

Hard：Product of Array Except Self（除自身以外数组的乘积）

问题：给定数组，返回每个位置"除自身外所有元素的乘积"，且不能使用除法。

模式：从左构建前缀积、从右构建后缀积，每个位置的答案 =left_product * right_product。

def product_except_self(nums): n = len(nums) result = [1] * n # left pass: result[i] = product of nums[0..i-1] prefix = 1 for i in range(n): result[i] = prefix prefix *= nums[i] # right pass: multiply by product of 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)$ 额外空间（输出数组不计入）。第一趟借用输出数组本身存中间前缀积，第二趟从右往左乘入后缀积。

陷阱：数组含 0 时基于除法的方案直接失效。前缀/后缀方案从不做除法，因此能天然正确处理零。

常见陷阱速查表

课后练习：按模式刷题巩固

按下列顺序练习，每题都强化本文的一个模式。先识别模式，再写代码，最后对照复杂度分析验证。以下是 NeetCode 系列题目 在本主题下的经典练习单（题目名称即检索关键词，可直接在题单中定位）：

Hash Map 查找

• Contains Duplicate — 热身：用哈希集合做"见过与否"判断
• Two Sum — complement 查找
• Group Anagrams — 规范形式作键
• Top K Frequent Elements — 哈希表 + 桶排序
• Longest Consecutive Sequence — 哈希集合 + 序列起点技巧
• Encode and Decode Strings — 设计一套序列化方案

双指针

• Valid Palindrome — 向内收拢的双指针
• Two Sum II（已排序）— 有序数组上的双指针
• Three Sum — 固定 + 双指针 + 去重
• Container With Most Water — 贪心双指针
• Trapping Rain Water — 带运行最大值的双指针

滑动窗口

• Best Time to Buy and Sell Stock — 退化窗口
• Longest Substring Without Repeating Characters — 哈希表辅助的扩张/收缩
• Longest Repeating Character Replacement — 窗口 + 最大频次技巧
• Minimum Window Substring — 扩张至合法，收缩至最小

前缀和

• Product of Array Except Self — 前缀积/后缀积

延伸阅读：在本仓库中继续深入

本主题与仓库其他章节紧密关联，建议按需查阅：

• 0. foundations.md：Big O 记号、递归、回溯与动态规划——本文所有复杂度结论的前提；
• 2. linked lists, stacks, and queues.md：数组与链表的性能对照、单调栈等延伸模式；
• chapter 13 - computing and OS/02. computer architecture.md：缓存层级（L1/L2/L3 延迟）、内存层级与局部性原理——理解"为什么数组快"的硬件根源；
• chapter 16 - SIMD and GPU programming/00. why C++ and how ML frameworks work.md：C++ 中数组/std::vector的连续内存与 SIMD 向量化——数组底层性能的实战延伸。

把数组的连续内存直觉、哈希表的 O(1) 查找能力，与四大模式（Hash Map 查找、双指针、滑动窗口、前缀和）结合起来，你就拥有了破解约 40% 算法面试题的核心工具箱。

【免费下载链接】maths-cs-ai-compendiumBecome a cracked AI/ML researcher/engineer with this unconventional textbook covering maths, computing, and ML with intuition.项目地址: https://gitcode.com/GitHub_Trending/mat/maths-cs-ai-compendium