数组与哈希

一句话总结：数组与哈希表是编程里最底层的两块砖，掌握它们背后的四大模式 (哈希查表、双指针、滑动窗口、前缀和)，就能拿下大约四成的编程面试题。

数组和哈希表是编程里最基础的两种数据结构。 本节先讲清楚它们的底层原理，然后由浅入深地建立起核心解题模式 —— 双指针、滑动窗口、前缀和、哈希查表 —— 每一步都会点出常见的坑.

• 如果你把数组和哈希映射 (hash map) 吃透，大约 40% 的编程面试题都能拿下。 这两个结构无处不在，因为它们提供了算法最需要的两件事：按下标快速访问 (数组) 和 按键快速查找 (哈希映射).

• 本节讲的是模式，不是具体解法。 目标是：遇到新题时你能一眼认出该用哪个模式、为什么用，而不是靠背题。

数组

• 数组 (array) 是一段连续的内存，元素按固定偏移存储。 访问第 \(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(1)\)	\(O(1)\)
追加 (append)	不适用	\(O(1)\) 摊还
在位置 \(i\) 插入	\(O(n)\)	\(O(n)\)
在位置 \(i\) 删除	\(O(n)\)	\(O(n)\)
查找 (无序)	\(O(n)\)	\(O(n)\)

• 坑：在数组中间插入或删除是 \(O(n)\)，因为后面所有元素都要往前后挪。 如果经常要在中间插入，换链表或者干脆换思路。

字符串

• 字符串 (string) 就是字符数组。 在 Python 里字符串是不可变的：每次拼接都产生一个新字符串。 在循环里逐字符拼字符串是 \(O(n^2)\)，因为每次拼接都把已经积攒的整段字符串复制一遍。

# 反例: O(n^2) 的字符串拼接
s = ""
for c in characters:
    s += c  # 每次都拷贝整段字符串

# 正例: 用 list 再 join, O(n)
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，意味着你可以用一个定长数组代替哈希映射。

哈希表

• 哈希表 (hash table) 把键映射到值，查找、插入、删除的平均开销都是 \(O(1)\). 它靠一个 哈希函数 (hash function) \(h(key)\) 把键转成数组下标。

• 哈希函数必须满足：确定性 (同一个键永远给出同一个哈希值)、均匀性 (键均匀分布到各个桶里)、计算快.

• 冲突 (collision) 是指两个不同的键哈希到同一个下标。 两种主流应对策略:

  • 拉链法 (chaining)：每个桶存一个键值对的链表。 冲突时追加到链表。 最坏情况 (所有键都撞进同一个桶): \(O(n)\). 好哈希函数下的平均情况：\(O(1)\).

  • 开放寻址 (open addressing)：冲突时向后探测下一个空位。 线性探测 (linear probing) 依次看下一个、再下一个……它对缓存友好，但会出现 聚簇 (clustering) (连成一片的已占用槽位). 罗宾汉哈希 (Robin Hood hashing) 通过挤开那些"离家更近"的条目，降低方差。

• 负载因子 (load factor) \(\alpha = n / m\) (元素数 / 桶数) 决定性能。 当 \(\alpha\) 越过阈值 (通常是 0.75)，表会 rehash：申请更大的表，把所有元素重新插入。 这一步是 \(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\) 个哈希函数加一个位数组。 常见于数据库 (避免为不存在的键去读磁盘)、Web 缓存、拼写检查器。

• 什么时候上哈希映射：只要你需要在 \(O(1)\) 内回答"我之前见过它吗?"或"跟这个键关联的计数/下标/值是什么?"，就该上。 如果你在反复线性扫描找东西，换成哈希映射几乎肯定能快。

---

模式：哈希映射查表

• 最基本的模式：用哈希映射把 \(O(n)\) 的扫描换成 \(O(1)\) 的查表。

Easy：两数之和 (Two Sum)

• 问题：给一个整数数组和一个目标值，返回两个数的下标，使它们加起来等于目标。

• 暴力法 \(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)\) 空间。

• 坑：别在检查补数之前就把当前数塞进哈希映射，否则可能把一个元素跟自己配对。 上面代码的顺序是对的：先查，后插。

Medium：字母异位词分组 (Group Anagrams)

• 问题：给一列字符串，把互为字母异位词的分为一组。 ("eat", "tea", "ate") 是一组。

• 模式要点：字母异位词由相同字符不同顺序构成。 把每个字符串排序，异位词就产生相同的排序键。 用这个排序键作为哈希映射的 key.

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\) 是字符串长度。 想更快，用字符频次计数元组当 key:

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 的 key). 必须转 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:
        # 只从序列开头开始计数
        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:
        # 跳过非字母数字字符
        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)

• 问题：找出数组里所有和为零的不重复三元组。

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

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 是关键。

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

---

模式：滑动窗口

• 滑动窗口 (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

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)

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

• 模式：用 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：这个字符可能是在当前窗口开始前就已经在映射里了。 少了这句判断，你会为一个其实不在当前窗口的字符错误地收缩窗口。

• 坑：用 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)       # 需要的字符及其个数
    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_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] 的和 (含 l, 不含 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：和为 K 的子数组 (Subarray Sum Equals 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}  # 空前缀和

    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 开始的子数组。

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

• 问题：给一个数组，返回一个新数组，每个位置是"其余所有元素的乘积". 不能用除法。

• 模式：从左往右建一遍前缀积，从右往左建一遍后缀积。 每个位置的答案就是 左积 * 右积.

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 vs right - left + 1	用 2 元素的小例子推一遍
Python 里的可变默认参数	def f(seen={}) 会跨调用共享状态	改成 def f(seen=None)
循环里拼字符串	Python 里 s += c 是 \(O(n^2)\)	用 list.append + "".join"
前缀和忘了 {0: 1}	漏掉从下标 0 开始的子数组	永远用空前缀初始化
先塞哈希映射再检查	两数之和先加 num 再查补数	先查，后插
没处理重复	三数之和返回重复三元组	跳过连续相等的值
整数溢出	C++/Java 里大数组求和	用 long 或做边界检查

---

课后练习 (NeetCode)

按顺序练。 每题对应本节的一个模式。

哈希映射查表

• Contains Duplicate —— 热身：用哈希集合判断是否见过
• Two Sum —— 补数查表
• Group Anagrams —— 规范形式作 key
• Top K Frequent Elements —— 哈希映射加桶排序
• Longest Consecutive Sequence —— 哈希集合加"序列起点"技巧
• Encode and Decode Strings —— 设计一种序列化方案

双指针

• Valid Palindrome —— 相向指针
• Two Sum II (sorted) —— 有序数组上的双指针
• 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 —— 前缀/后缀积

---

📌 本节要点

• 数组本质：连续内存加固定偏移，按下标访问 \(O(1)\)，中间插入删除 \(O(n)\).
• 动态数组扩容：摊还倍增策略让追加的摊还开销降到 \(O(1)\).
• 缓存局部性：数组在实践中比链表快 10 到 100 倍，是常数因子而非渐近复杂度决定的。
• 字符串拼接: Python 里循环内 s += c 是 \(O(n^2)\) 陷阱，一律用 list + join.
• 哈希表核心：好哈希函数加合理负载因子，让查找/插入/删除的平均开销都是 \(O(1)\).
• 哈希查表模式：用 \(O(1)\) 查表替换 \(O(n)\) 扫描，典型如两数之和的补数查表。
• 双指针模式：相向或同向双指针，常用于有序数组的成对元素/子数组问题。
• 滑动窗口模式：动态维护连续区间，适用于"最长/最短满足条件的子数组"这类问题。
• 前缀和模式：一次 \(O(n)\) 预处理，之后子数组求和 \(O(1)\)，常与哈希映射联用。
• 去重与初始化：三数之和忘去重、前缀和忘 {0: 1} 是新手最常踩的坑。