数组与哈希

数组与哈希

数组（array）和哈希表（hash table）是编程中最基础的两种数据结构。本文件先讲清它们的底层原理，再通过难度递增的题目构建出关键解题模式：双指针、滑动窗口、前缀和以及基于哈希的查找，并在每一步指出常见陷阱。

• 如果你深刻理解了数组和哈希表，就能解决约 40% 的编程面试题。这两种结构无处不在，因为它们恰好提供了算法最需要的两样东西：快速的按下标访问（数组）和按键快速查找（哈希表）。

• 本文件教的是模式，而不是解法。目标是当你看到一道新题时，能认出该用哪个模式、为什么用，而不是试图回忆某个背下来的答案。

数组

• 数组是一块连续的内存，元素按固定偏移量存放。访问第 i 个元素只需 O(1)，因为地址就是 base + i * element_size。这是数据访问能达到的最快速度，也是数组成为默认选择的原因。

• 动态数组（dynamic array）（Python 的 list、Java 的 ArrayList、C++ 的 vector）在满的时候会自动扩容。策略是均摊倍增（amortised doubling）：数组满时，分配一个两倍大的新数组，把所有元素拷过去。拷贝本身是 O(n)，但它发生得极少（每 n 次插入才一次），所以每次插入的均摊成本是 O(1)。

• **缓存局部性（cache locality）**是数组在实践中（而不仅仅是理论上）很快的原因。因为元素连续存放，访问一个元素会把附近的元素一起加载进 CPU 缓存（第 13 章）。遍历数组是缓存友好的，而沿着链表的指针跳来跳去则不是。这个常数因子的差距在实践中可以达到 10-100 倍。

• 陷阱：在数组中间插入或删除是 O(n)，因为后面所有元素都要移动。如果你需要频繁在中间插入，考虑改用链表或换个思路。

字符串

• 字符串本质上是一个字符数组。在 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，这意味着你可以用一个定长数组代替哈希表。

哈希表

• 哈希表把键映射到值，平均情况下查找、插入、删除都是 O(1)。它通过一个哈希函数（hash function） h(key) 把键转成数组下标。

• 哈希函数必须满足：确定性（同一个键永远得到同一个哈希值）、均匀（把键均匀分散到各个桶里）、计算快。

• 当两个不同的键哈希到同一个下标时就会发生冲突（collision）。两种主要应对策略：

  • 链地址法（chaining）：每个桶存一个键值对的链表。冲突时追加到链表。最坏情况（所有键都哈希到同一个桶）：O(n)。哈希函数良好时的平均情况：O(1)。

  • 开放寻址法（open addressing）：冲突时探测下一个空位。线性探测（linear probing）依次检查下一个、再下一个……它对缓存友好，但容易产生聚集（clustering）（长串连续占用的位置）。Robin Hood 哈希通过让「离家近」的条目抢占「离家远」的条目来降低方差。

• 装填因子（load factor） \alpha = n / m（条目数 / 桶数）决定了性能。当 \alpha 超过阈值（通常是 0.75）时，表会重哈希（rehash）：分配一张更大的表，把所有元素重新插入。这要花 O(n)，但发生得很少。

• 哈希映射（hash map）（Python 的 dict、Java 的 HashMap）存键值对。哈希集合（hash set）（Python 的 set、Java 的 HashSet）只存键（用于快速判断成员归属）。

• **布隆过滤器（Bloom filter）**是节省空间的概率型集合。它能告诉你「肯定不在集合里」或「可能在集合里」（假阳性率可调）。它用 k 个哈希函数和一个位数组。常用于数据库（避免对不存在的键读盘）、网页缓存和拼写检查。

• 什么时候该用哈希表：每当你需要在 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)。字符计数元组是一种规范形式（canonical form）：对同一组里的所有成员，这个表示都相同。

• 陷阱：在 Python 里，list 不可哈希（不能作为 dict 的键）。你必须转成 tuple。很多人在写 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] 会从每个起点都扫描整条序列）。

模式：双指针

• **双指针（two pointers）**模式用两个下标在数组里移动，通常从两端出发或从同一端以不同速度出发。当数组已排序，或需要比较数对时，它很管用。

• 何时使用：问题涉及数对、子数组或划分，且数组已排序（或排序后不会丢失所需信息）。

简单：验证回文

• 题目：判断一个字符串是否是回文（只考虑字母数字字符，忽略大小写）。

• 模式：一个指针在开头，一个在末尾。向中间靠拢，逐字符比较。

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 检查。没有它，遇到像 "!!!"（全是非字母数字）这样的字符串，指针会越界。

中等：三数之和

• 题目：找出数组中所有和为零且互不相同的三元组。

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

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) 空间。另外，把更新最大值时的 >= 写成 > 会导致接水量差一。

模式：滑动窗口

• **滑动窗口（sliding window）**模式维护一个窗口（连续子数组），在遍历时不断扩张和收缩。适用于询问满足某条件的子数组或子串的问题。

• 何时使用：问题要求满足某约束的最长/最短子数组或子串，且窗口的扩张/收缩是单调的（加元素只会让约束更难/更易满足，而非两者皆有）。

• 模板：

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{不同字符数}|)。have 计数器让合法性检查变成 O(1)。

• 陷阱：检查 window_counts[char] == need[char]（而不是 >=）确保我们对每个字符恰好增加一次 have。如果用 >=，就会多算。

模式：前缀和

• **前缀和（prefix sum）**数组存放累加和：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] 的和（左闭右开）
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}  # 空前缀和

    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) 额外空间（输出数组不计）。它复用输出数组来存中间的前缀乘积，再在第二趟里乘进后缀乘积。

• 陷阱：如果数组里有零，基于除法的做法会失败。这种前缀/后缀做法能正确处理零，因为它从不做除法。

常见陷阱汇总

编程练习（使用 CoLab 或 notebook）

按顺序练习以下题目，每道题都巩固了本文件里的一个模式。可在 NeetCode 的题目列表中找到这些题目。

哈希表查找

• Contains Duplicate（存在重复元素）—— 热身：用哈希集合做「见过」判断
• Two Sum（两数之和）—— 互补数查找
• Group Anagrams（字母异位词分组）—— 用规范形式作键
• Top K Frequent Elements（前 K 个高频元素）—— 哈希表 + 桶排序
• 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（除自身以外的数组乘积）—— 前缀/后缀乘积