第2章：数组与哈希表的巧妙运用

数组和哈希表是算法题中出现频率最高的两种数据结构。它们看似简单，实则变化无穷。掌握了这两种数据结构的精髓，你就能解决 LeetCode 上超过一半的题目。本章将深入探讨它们的高级用法，让你能够快速识别题目模式，选择最优解法。

对于有经验的工程师来说，数组和哈希表的基本操作早已烂熟于心。但算法题的巧妙之处在于如何创造性地使用这些基础工具。比如，利用数组索引本身编码信息，用负数标记实现原地去重，或者通过前缀和将区间问题转化为两点查询。这些技巧看似取巧，实则体现了对数据结构本质的深刻理解。

本章的学习目标是：

掌握数组的原地操作技巧，避免使用额外空间
熟练运用哈希表的三种核心模式：去重、计数、映射
理解前缀和与差分数组的本质，快速处理区间问题
掌握滑动窗口与双指针的通用模板

2.1 数组索引的多重含义与原地操作

索引即信息：利用位置编码额外信息

在传统的编程中，我们习惯将数组索引仅仅看作访问元素的手段。但在算法题中，索引本身就可以携带信息。这种思维转换是解决很多"原地"问题的关键。

考虑这样一个问题：给定一个包含 n 个整数的数组，其中每个整数都在 [1, n] 范围内，如何在 O(1) 空间内找出所有重复的数字？

常规思路是使用哈希表记录出现过的数字，但这需要 O(n) 的额外空间。如果我们换个角度思考：既然数字都在 [1, n] 范围内，我们可以将数字 x 映射到索引 x-1 的位置。通过在对应位置做标记（比如将该位置的数字变为负数），就能记录这个数字是否出现过。

def findDuplicates(nums):
    result = []
    for num in nums:
        index = abs(num) - 1  # 映射到索引
        if nums[index] < 0:   # 已经被标记过，说明是重复的
            result.append(abs(num))
        else:
            nums[index] = -nums[index]  # 标记
    return result

这种技巧的本质是：利用数组自身作为哈希表。索引充当键，而正负号充当值。这种思想可以推广到更复杂的场景。

原地标记的三种技巧

1. 负数标记法

最常见的原地标记方法。适用于数组元素都是正数的情况。通过将 nums[i] 变为负数来表示数字 i+1 已经出现过。

示例：LeetCode #448 找到所有数组中消失的数字

def findDisappearedNumbers(nums):
    # 第一遍：标记出现过的数字
    for num in nums:
        index = abs(num) - 1
        nums[index] = -abs(nums[index])

    # 第二遍：找出未被标记的位置
    return [i + 1 for i, num in enumerate(nums) if num > 0]

2. 取模编码法

当需要在同一个位置存储多个信息时，可以使用取模编码。原理是利用整数除法和取模运算的可逆性。

假设原数组的值域是 [0, n-1]，我们可以用 nums[i] = nums[i] + (新值) * n 来同时存储原值和新值：

原值 = nums[i] % n
新值 = nums[i] // n

示例：LeetCode #41 缺失的第一个正数

def firstMissingPositive(nums):
    n = len(nums)

    # 第一步：将所有非正数和大于n的数改为n+1（一个不影响结果的占位符）
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = n + 1

    # 第二步：用取模编码标记
    for i in range(n):
        val = abs(nums[i])
        if val <= n:
            # 将索引 val-1 位置的数加上 n+1
            nums[val - 1] += (n + 1) if nums[val - 1] > 0 else -(n + 1)

    # 第三步：找第一个未被标记的位置
    for i in range(n):
        if nums[i] % (n + 1) == n + 1:
            return i + 1

    return n + 1

3. 交换归位法

将每个元素放到它"应该"在的位置上。这种方法特别适合处理排列和缺失数字的问题。

示例：LeetCode #287 寻找重复数

这道题有个特殊限制：数组包含 n+1 个数字，每个数字都在 [1, n] 范围内，只有一个数字重复。更重要的是，不能修改原数组。

这时我们需要用另一种思路：将数组看作一个链表，其中 nums[i] 表示节点 i 的下一个节点。由于有重复数字，这个"链表"一定有环。问题转化为找环的入口，可以用 Floyd 的龟兔赛跑算法：

def findDuplicate(nums):
    # 阶段1：龟兔赛跑找相遇点
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # 阶段2：找环的入口
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

这个解法的精妙之处在于将数组问题转化为图论问题。索引和值之间的映射关系构成了一个有向图，重复的数字导致了环的产生。

鸽巢原理的应用

鸽巢原理（Pigeonhole Principle）是这类问题的理论基础：如果有 n+1 个物品要放进 n 个盒子，那么至少有一个盒子包含多个物品。

在数组问题中，这个原理常常以下面的形式出现：

长度为 n 的数组，元素范围是 [1, n-1]，则必有重复
长度为 n+1 的数组，元素范围是 [1, n]，则必有重复

理解了这个原理，很多看似复杂的问题就有了清晰的思路。比如：

问题：一个长度为 n 的数组，包含 0 到 n 之间的整数，找出唯一缺失的数字。

解法：利用数学性质 - 期望的总和与实际总和之差

def missingNumber(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum

但如果要求 O(1) 空间且不能溢出呢？可以用异或运算：

def missingNumber(nums):
    result = len(nums)  # 初始化为n
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

2.2 哈希表的三种核心用法：去重、计数、映射

哈希表是空间换时间的典范。在 Python 中，dict 和 set 都是基于哈希表实现的，提供了平均 O(1) 的查找、插入和删除操作。理解哈希表的三种核心用法，能帮助你快速识别何时该使用哈希表。

去重：Set 的应用场景

Set 最直观的用途就是去重。但在算法题中，Set 的作用远不止于此。它可以用来：

快速判断元素是否存在
维护滑动窗口中的唯一元素
记录访问过的状态（在 BFS/DFS 中防止重复访问）

示例：LeetCode #128 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。要求时间复杂度 O(n)。

def longestConsecutive(nums):
    if not nums:
        return 0

    num_set = set(nums)  # 去重并提供 O(1) 查找
    max_length = 0

    for num in num_set:
        # 只从序列的起点开始计算
        if num - 1 not in num_set:
            current_num = num
            current_length = 1

            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1

            max_length = max(max_length, current_length)

    return max_length

这个解法的关键insight是：只从连续序列的起点开始计算长度，避免重复计算。判断是否是起点的方法很简单：num - 1 不在集合中。

计数：频率统计与 Counter 模式

当需要统计元素出现次数时，哈希表是最自然的选择。Python 的 collections.Counter 提供了更方便的接口。

示例：LeetCode #49 字母异位词分组

from collections import defaultdict

def groupAnagrams(strs):
    anagram_map = defaultdict(list)

    for s in strs:
        # 将排序后的字符串作为键
        key = tuple(sorted(s))
        anagram_map[key].append(s)

    return list(anagram_map.values())

更优雅的解法是使用字符计数作为键：

def groupAnagrams(strs):
    anagram_map = defaultdict(list)

    for s in strs:
        # 统计每个字符的出现次数
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1

        # 将计数数组转为元组作为键
        key = tuple(count)
        anagram_map[key].append(s)

    return list(anagram_map.values())

映射：建立双向索引

哈希表可以建立元素之间的映射关系，这在处理配对、查找等问题时非常有用。

两数之和的变体

经典的两数之和问题展示了哈希表映射的威力：

def twoSum(nums, target):
    num_to_index = {}

    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], i]
        num_to_index[num] = i

    return []

这个模式可以扩展到更复杂的场景：

示例：LeetCode #1 两数之和的扩展 - 找出所有和为目标值的数对

def findAllPairs(nums, target):
    seen = {}
    pairs = []

    for num in nums:
        complement = target - num
        if complement in seen and seen[complement] > 0:
            pairs.append([complement, num])
            seen[complement] -= 1
        else:
            seen[num] = seen.get(num, 0) + 1

    return pairs

2.3 前缀和与差分数组：区间操作优化

前缀和（Prefix Sum）和差分数组（Difference Array）是处理区间问题的两大利器。它们的核心思想都是预处理，将原本需要 O(n) 的区间操作优化到 O(1)。

前缀和的本质：积分与微分的离散版本

如果你有微积分背景，前缀和就是离散函数的"积分"，而原数组是"导数"。这个类比能帮助你更深刻地理解前缀和的本质。

给定数组 nums[0..n-1]，前缀和数组 prefix[0..n] 定义为：

prefix[0] = 0
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

有了前缀和，区间 [i, j] 的和就是：prefix[j+1] - prefix[i]

示例：LeetCode #560 和为K的子数组

统计和为 K 的连续子数组个数。暴力解法需要 O(n²)，但用前缀和 + 哈希表可以优化到 O(n)：

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    sum_count = {0: 1}  # 前缀和为0的情况出现1次（空数组）

    for num in nums:
        prefix_sum += num

        # 寻找 prefix_sum - k 是否存在
        # 如果存在，说明有子数组的和为 k
        if prefix_sum - k in sum_count:
            count += sum_count[prefix_sum - k]

        # 记录当前前缀和出现的次数
        sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1

    return count

这个解法的关键洞察是：如果 prefix[j] - prefix[i] = k，那么 prefix[i] = prefix[j] - k。所以我们只需要在哈希表中查找 prefix[j] - k 出现了多少次。

前缀积的巧妙应用

示例：LeetCode #238 除自身以外数组的乘积

要求不使用除法，在 O(n) 时间内完成。

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n

    # 第一遍：计算左侧所有元素的乘积
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= nums[i]

    # 第二遍：乘以右侧所有元素的乘积
    right_product = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]

    return result

这实际上是计算了两个前缀积：从左到右和从右到左。

差分数组：区间更新的利器

差分数组是前缀和的逆运算。如果说前缀和是为了快速查询区间和，那么差分数组就是为了快速进行区间更新。

给定数组 nums[0..n-1]，差分数组 diff[0..n-1] 定义为：

diff[0] = nums[0]
diff[i] = nums[i] - nums[i-1] (i > 0)

对区间 [i, j] 的所有元素加上 val，只需要：

diff[i] += val
diff[j+1] -= val (如果 j+1 < n)

最后通过前缀和还原出更新后的数组。

示例：区间加法

def rangeAddition(length, updates):
    diff = [0] * length

    # 应用所有更新
    for start, end, val in updates:
        diff[start] += val
        if end + 1 < length:
            diff[end + 1] -= val

    # 通过前缀和还原数组
    result = [0] * length
    result[0] = diff[0]
    for i in range(1, length):
        result[i] = result[i-1] + diff[i]

    return result

二维前缀和：矩阵区域和

前缀和的思想可以扩展到二维。对于矩阵 matrix[m][n]，二维前缀和 prefix[i][j] 表示以 (0,0) 为左上角、(i-1,j-1) 为右下角的矩形区域的和。

class NumMatrix:
    def __init__(self, matrix):
        if not matrix or not matrix[0]:
            return

        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.prefix[i][j] = (
                    matrix[i-1][j-1] 

                    + self.prefix[i-1][j] 
                    + self.prefix[i][j-1] 
                    - self.prefix[i-1][j-1]
                )

    def sumRegion(self, row1, col1, row2, col2):
        return (
            self.prefix[row2+1][col2+1] 

            - self.prefix[row1][col2+1] 
            - self.prefix[row2+1][col1] 
            + self.prefix[row1][col1]
        )

这里用到了容斥原理：矩形区域的和 = 大矩形 - 上方矩形 - 左方矩形 + 左上角矩形（因为左上角被减了两次）。

2.4 滑动窗口与双指针模板

滑动窗口和双指针是处理数组/字符串问题的两个重要技巧。它们的共同特点是通过维护指针的单调移动，将暴力的 O(n²) 算法优化到 O(n)。

滑动窗口的适用条件：单调性

滑动窗口能够工作的关键是问题具有单调性：当窗口扩大时，某个性质单调变化（比如和变大、不同字符数增加等）。

滑动窗口的通用模板：

def slidingWindow(s):
    left = right = 0
    window = {}  # 或其他数据结构，用于维护窗口状态
    result = 0   # 或其他初始值

    while right < len(s):
        # 扩张窗口
        char = s[right]
        right += 1
        # 更新窗口状态
        window[char] = window.get(char, 0) + 1

        # 收缩窗口（当窗口不满足条件时）
        while not isValid(window):
            char = s[left]
            left += 1
            # 更新窗口状态
            window[char] -= 1
            if window[char] == 0:
                del window[char]

        # 更新结果
        result = max(result, right - left)

    return result

示例：LeetCode #3 无重复字符的最长子串

def lengthOfLongestSubstring(s):
    char_index = {}  # 字符到索引的映射
    left = 0
    max_length = 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
        max_length = max(max_length, right - left + 1)

    return max_length

双指针的三种模式

1. 同向双指针（快慢指针）

用于去重、移除元素等场景。快指针遍历，慢指针维护结果。

def removeDuplicates(nums):
    if len(nums) <= 1:
        return len(nums)

    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1

2. 相向双指针

用于有序数组的查找、回文判断等。

示例：LeetCode #15 三数之和

def threeSum(nums):
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # 跳过重复元素
        if i > 0 and nums[i] == nums[i-1]:
            continue

        left, right = i + 1, n - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                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
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

3. 分离双指针

两个指针在不同的数组/链表上移动。

def merge(nums1, m, nums2, n):
    # 从后往前合并，避免覆盖
    p1, p2, p = m - 1, n - 1, m + n - 1

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    # 如果 nums2 还有剩余
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

滑动窗口的变体：固定大小 vs 可变大小

固定大小窗口：窗口大小为 k，求最大/最小值

def maxSlidingWindow(nums, k):
    from collections import deque

    dq = deque()  # 存储索引，保持单调递减
    result = []

    for i, num in enumerate(nums):
        # 移除超出窗口的元素
        while dq and dq[0] <= i - k:
            dq.popleft()

        # 保持单调性
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # 窗口形成后记录结果
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

可变大小窗口：满足某个条件的最长/最短子数组

def minSubArrayLen(target, nums):
    left = 0
    min_length = float('inf')
    current_sum = 0

    for right, num in enumerate(nums):
        current_sum += num

        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1

    return min_length if min_length != float('inf') else 0

本章小结

本章深入探讨了数组和哈希表的高级用法，这些技巧构成了解决大量算法题的基础。让我们回顾一下关键概念：

核心思想

空间与时间的权衡：哈希表用 O(n) 空间换取 O(1) 查找；前缀和用 O(n) 预处理换取 O(1) 区间查询。
索引的多重含义：数组索引不仅是位置，还可以编码值、状态、映射关系。
原地操作的艺术：通过负数标记、取模编码、交换归位等技巧，在 O(1) 空间内完成复杂操作。
单调性的利用：滑动窗口和双指针的本质是利用问题的单调性，避免重复计算。

关键公式和模板

前缀和：

构建：prefix[i] = prefix[i-1] + nums[i-1]
区间和：sum(i, j) = prefix[j+1] - prefix[i]

差分数组：

区间更新：diff[i] += val, diff[j+1] -= val
还原：nums[i] = nums[i-1] + diff[i]

滑动窗口模板：

while right < n:
    # 扩张窗口
    window.add(arr[right])
    right += 1

    # 收缩窗口
    while window_invalid():
        window.remove(arr[left])
        left += 1

    # 更新答案
    update_answer()

双指针模板：

同向：快指针探索，慢指针维护
相向：利用有序性，根据和的大小调整
分离：在不同序列上协调移动

算法复杂度总结

技巧	时间复杂度	空间复杂度	适用场景
原地标记	O(n)	O(1)	值域有限的查找/去重
哈希表	O(n)	O(n)	通用的查找/计数/映射
前缀和	O(n) 预处理 O(1) 查询	O(n)	频繁的区间和查询
差分数组	O(k) 更新 O(n) 还原	O(n)	批量区间更新
滑动窗口	O(n)	O(1) 或 O(k)	连续子数组/子串问题
双指针	O(n) 或 O(nlogn)	O(1)	有序数组、去重、合并

常见陷阱与错误 (Gotchas)

1. 边界条件处理

错误示例：前缀和数组的长度

# 错误：容易导致索引越界
prefix = [0] * len(nums)
for i in range(len(nums)):
    prefix[i] = prefix[i-1] + nums[i]  # i=0 时出错

# 正确：前缀和数组长度应为 n+1
prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
    prefix[i+1] = prefix[i] + nums[i]

错误示例：滑动窗口的初始化

# 错误：忘记处理空数组
def maxSubArray(nums):
    max_sum = 0  # 如果全是负数会出错
    current_sum = 0

# 正确：使用合理的初始值
def maxSubArray(nums):
    if not nums:
        return 0
    max_sum = float('-inf')
    current_sum = 0

2. 整数溢出问题

在其他语言（如 C++、Java）中，需要特别注意整数溢出：

# Python 不会溢出，但在其他语言中需要注意
# C++ 中应该使用 long long
# Java 中应该使用 long

# 常见溢出场景：
# 1. 前缀和可能超过 int 范围
# 2. 两数之和可能溢出
# 3. 乘积运算容易溢出

# 防溢出技巧：
# 使用 mid = left + (right - left) // 2 
# 而不是 mid = (left + right) // 2

3. 哈希冲突的影响

虽然理论上哈希表操作是 O(1)，但最坏情况可能退化到 O(n)：

# 潜在问题：大量哈希冲突
# Python 的 dict 实现很好，但仍要注意：

# 1. 自定义对象作为键时，确保正确实现 __hash__ 和 __eq__
# 2. 使用 tuple 而不是 list 作为键（list 不可哈希）
# 3. 大数据量时考虑负载因子的影响

4. 原地操作的陷阱

错误示例：修改正在遍历的数组

# 错误：边遍历边删除
for i, num in enumerate(nums):
    if should_remove(num):
        nums.pop(i)  # 会导致索引错乱

# 正确：从后往前删除，或使用双指针
for i in range(len(nums) - 1, -1, -1):
    if should_remove(nums[i]):
        nums.pop(i)

5. 滑动窗口的单调性假设

滑动窗口不是万能的，它要求问题具有单调性：

# 适合滑动窗口：找最长无重复子串
# 因为加入新字符只会增加或不变字符种类

# 不适合滑动窗口：找恰好包含 k 个不同字符的最长子串
# 需要转化为：最多 k 个不同字符 - 最多 k-1 个不同字符

6. 调试技巧

打印中间状态：

def debug_sliding_window(s):
    left = right = 0
    window = {}

    while right < len(s):
        # 打印窗口状态
        print(f"Window [{left}:{right}]: {s[left:right]}")
        print(f"State: {window}")

        # ... 窗口操作 ...

使用断言验证不变量：

def process_array(nums):
    # 验证前缀和的正确性
    prefix = build_prefix_sum(nums)
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            assert sum(nums[i:j+1]) == prefix[j+1] - prefix[i]

可视化数组状态：

def visualize_two_pointers(nums, left, right):
    visual = []
    for i, num in enumerate(nums):
        if i == left:
            visual.append(f"[{num}]")
        elif i == right:
            visual.append(f"({num})")
        else:
            visual.append(str(num))
    print(" ".join(visual))

7. 性能优化提醒

避免不必要的数据结构转换：

# 低效：多次转换
result = list(set(list_data))

# 高效：直接使用合适的数据结构
seen = set()
result = []
for item in list_data:
    if item not in seen:
        seen.add(item)
        result.append(item)

选择合适的数据结构： - 需要有序：用 list 或 collections.deque - 需要去重：用 set - 需要计数：用 collections.Counter - 需要有序字典：用 collections.OrderedDict（Python 3.7+ 的 dict 已经有序）
注意 Python 特有的性能陷阱：

# 低效：字符串拼接
result = ""
for char in chars:
    result += char  # O(n²)

# 高效：使用 join
result = "".join(chars)  # O(n)

通过掌握这些技巧和避免常见陷阱，你将能够高效、准确地解决涉及数组和哈希表的算法题。记住，这些基础数据结构的灵活运用，往往是解决复杂问题的关键。