问题简述

1 问题背景

一架货运飞机的平衡仓位对重量要求极其严苛，最后剩余的2000公斤容积必须由两个集装箱填满，以保证飞行重心稳定，每个箱子重量不等。他需要从中选出两个集装箱，其重量之和恰好为2000公斤。

2 问题抽象

该背景被抽象为以下数学模型：

• 输入：一个整数数组（nums），代表每个箱子的重量；以及一个目标值（target），即 2000
• 任务：在数组中寻找两个数，使其之和等于目标值。
• 输出：返回这两个数在原始数组中的下标 (Indices)

---

基本知识

1 哈希表

1.1 原理与定义

• 哈希表内存模型：哈希表是字典在内存中的实现方式。它利用哈希函数计算键的哈希值，并将该值映射到数组的特定索引中，从而实现快速查找。
• 哈希定义：哈希是一种分配和索引数据的方法，核心思想是允许通过公式（哈希函数）生成的键来索引大量数据。

1.2 术语与函数

• 术语定义：
  • 哈希函数：将任意大小的数据（n）映射为固定大小数据（m）的函数。
  • 键 (Key)：用户输入的数据。
  • 哈希值：哈希函数返回的结果。
  • 冲突 (Collision)：当两个不同的键通过哈希函数产生了相同的输出（哈希值）时，即发生冲突。
• 典型哈希函数：
  • 直接定址法：$Hash(key) = a * key + b$。
  • 除留余数法：$Hash(key) = key \pmod m$（m 通常选为质数）

  如果$m$是一个合数，而输入数据的键刚好与$m$有公约数，那么这些键求余后的结果会集中在$m$的某些特定倍数槽位上，导致分布不均，选为质数可以使$m$与其他数字产生公约数的概率最低，最大限度地减少这种规律性带来的聚集效应。

  • 全域哈希 (Universal Hashing)：通过随机选择哈希函数来降低冲突概率。
• 优秀哈希的标准：计算速度快、键分布均匀、冲突最少。

1.3 实际应用场景

• 密码验证：系统不存储明文密码，而是存储密码的哈希指纹。该应用依赖于两个核心机制：
  • 单向性（不可逆）：无法从哈希值反推原始密码。

  由于信息在映射过程中被压缩了（多个不同的键可能对应同一个哈希值，即冲突），无法唯一确定原始输入

  • 雪崩效应：原始密码哪怕只改变一个字母，生成的哈希值也会发生剧烈变化。
• 文件系统定位：用于将文件路径映射到磁盘的物理位置。通过文件唯一标识的哈希值前几位来创建多级子目录（如 /77/e1/...），实现均匀分布并加速对数以亿计文件的访问。

1.4 冲突解决方法

• 链地址法 (Direct Chaining)：在哈希表的每个单元中，并不直接存储数据，而是存储一个指向链表的指针，当一个键（Key）通过哈希函数计算出索引后，该键值对会被添加到该索引对应的链表中，哈希表永远不会填满，但如果链表过长，搜索的时间复杂度会退化为 $O(n)$。当删除操作频繁时，通常首选此方法。
• 开放定址法 (Open Addressing)：
  • 线性探测：发生冲突时，将新键放入最近的下一个空单元中。
  • 双重哈希：利用第二个哈希函数来计算探测间隔。
  • 动态扩容：当表满时，创建一个 2 倍大小的新表并对所有键进行重新哈希（Rehashing）。这种方法在已知输入规模时更为适用。

1.5 算法复杂度

• 效率优势：哈希表的主要动力在于其搜索操作的高效性。
• 复杂度对比：相比于数组和链表（搜索复杂度 $O(n)$）或树（搜索复杂度 $O(\log n)$），哈希表在平均情况下的搜索、插入和删除都能达到 $O(1)$。但若哈希函数设计不当，复杂度可能退化为 $O(n)$。

2 排序算法

稳定与否取决于相同大小数据在排序前后是否保持原有相对位置

2.1 冒泡排序

重复遍历数组，依次比较相邻的两个元素，如果顺序错误（前大于后）就交换。每一轮遍历会将未排序部分的最大值冒泡到正确位置。时间复杂度$O(n^2)$，稳定

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

初始: [5, 3, 8, 4, 2]
第1趟:
  比较 5,3 → 交换 → [3, 5, 8, 4, 2]
  比较 5,8 → 保持 → [3, 5, 8, 4, 2]
  比较 8,4 → 交换 → [3, 5, 4, 8, 2]
  比较 8,2 → 交换 → [3, 5, 4, 2, 8]   ← 8 已就位
第2趟:
  比较 3,5 → 保持
  比较 5,4 → 交换 → [3, 4, 5, 2, 8]
  比较 5,2 → 交换 → [3, 4, 2, 5, 8]   ← 5 就位
...
最后: [2, 3, 4, 5, 8]

2.2 选择排序

每一轮从未排序区间选出最小（或最大）元素，将其与未排序区间的第一个元素交换，逐步扩大已排序区间。时间复杂度$O(n^2)$，不稳定

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

初始: [29, 10, 14, 37, 13]
第1轮: 在 [29,10,14,37,13] 中找到最小 10 → 与 29 交换
      → [10, 29, 14, 37, 13]  ↑已排序
第2轮: 在 [29,14,37,13] 中找到最小 13 → 与 29 交换
      → [10, 13, 14, 37, 29]
第3轮: 在 [14,37,29] 中找到最小 14 → 已在正确位置
      → [10, 13, 14, 37, 29]
第4轮: 在 [37,29] 中找到最小 29 → 与 37 交换
      → [10, 13, 14, 29, 37]
完成

2.3 插入排序

将数组分为已排序和未排序两部分，每次取未排序部分的第一个元素，在已排序部分中找到合适位置并插入。适合小规模或基本有序的数据，时间复杂度$O(n^2)$，稳定

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

数组: [4, 3, 2, 10, 12, 1, 5, 6]
竖线 "|" 左边是已排序部分，右边是未排序部分
初始: [4 | 3, 2, 10, 12, 1, 5, 6]      已排序: [4]
i=1: key=3, 4>3 → 4右移, 插入3
     [3, 4 | 2, 10, 12, 1, 5, 6]        已排序: [3,4]
i=2: key=2, 4>2右移, 3>2右移, 插入2
     [2, 3, 4 | 10, 12, 1, 5, 6]        已排序: [2,3,4]
i=3: key=10, 4<10 → 不动
     [2, 3, 4, 10 | 12, 1, 5, 6]        已排序: [2,3,4,10]
i=4: key=12, 10<12 → 不动
     [2, 3, 4, 10, 12 | 1, 5, 6]        已排序: [2,3,4,10,12]
i=5: key=1, 12>1右移, 10>1右移, 4>1右移, 3>1右移, 2>1右移
     插入1
     [1, 2, 3, 4, 10, 12 | 5, 6]        已排序: [1,2,3,4,10,12]
i=6: key=5, 12>5右移, 10>5右移, 4<5停止, 插入5
     [1, 2, 3, 4, 5, 10, 12 | 6]        已排序: [1,2,3,4,5,10,12]
i=7: key=6, 12>6右移, 10>6右移, 5<6停止, 插入6
     [1, 2, 3, 4, 5, 6, 10, 12]         排序完成

2.4 桶排序

将数据分到有限数量的桶里，每个桶分别排序（常用插入排序或递归），最后按顺序合并所有桶。适用于数据均匀分布的情况，平均时间复杂度 $O(n+k)$，稳定

def bucket_sort(arr, bucket_size=5):
    if len(arr) == 0:
        return arr

    min_val, max_val = min(arr), max(arr)
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        idx = (num - min_val) // bucket_size
        buckets[idx].append(num)

    sorted_arr = []
    for bucket in buckets:
        insertion_sort(bucket)   # 使用插入排序（或其他排序）
        sorted_arr.extend(bucket)
    return sorted_arr

输入: [22, 45, 12, 8, 10, 6, 72, 33, 50, 40]
确定桶范围: min=6, max=72, 桶大小=10 → 桶数 = (72-6)//10+1 = 7

桶0 (0~15):  8, 10, 12, 6
桶1 (16~25): 22
桶2 (26~35): 33
桶3 (36~45): 40, 45
桶4 (46~55): 50
桶5 (56~65): (空)
桶6 (66~75): 72

各桶内排序后连接:
桶0 → [6,8,10,12]
桶1 → [22]
桶2 → [33]
桶3 → [40,45]
桶4 → [50]
桶6 → [72]
最终: [6,8,10,12,22,33,40,45,50,72]

2.5 归并排序

采用分治策略，将数组不断从中间分割为两个子数组，递归排序子数组，最后合并两个有序子数组。时间复杂度 $O(nlogn)$，稳定

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

               [38,27,43,3,9,82,10]
                 /             \
          [38,27,43,3]      [9,82,10]
            /      \          /     \
       [38,27]  [43,3]    [9,82]   [10]
       /    \    /    \    /   \     |
    [38] [27] [43]   [3]  [9]  [82] [10]
      \   /     \   /      \   /     |
    [27,38]   [3,43]      [9,82]   [10]
       \        /             \     /
    [3,27,38,43]            [9,10,82]
             \               /
         [3,9,10,27,38,43,82]

2.6 快速排序

选择一个基准元素（pivot），将数组划分为小于基准和大于基准的两部分，然后递归地对两部分进行排序。平均时间复杂度$O(nlogn)$，最坏$O(n^2)$，不稳定

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

选取基准 pivot = 6 (以 6 为例)

初始: [4, 2, 9, 6, 5, 1, 8, 3, 7]
pivot = 6
分区:
  less:    [4,2,5,1,3]    (小于 6)
  equal:   [6]
  greater: [9,8,7]

递归排序 less 和 greater:
  less:  [1,2,3,4,5]
  greater: [7,8,9]
合并: [1,2,3,4,5,6,7,8,9]

2.7 堆排序

利用最大堆（或最小堆）数据结构，先将数组构建成最大堆，然后不断将堆顶与末尾元素交换，并缩小堆的范围。时间复杂度$O(nlogn)$，不稳定

def heap_sort(arr):
    n = len(arr)

    def heapify(i, size):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < size and arr[left] > arr[largest]:
            largest = left
        if right < size and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(largest, size)

    for i in range(n // 2 - 1, -1, -1):
        heapify(i, n)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(0, i)
    return arr

原始数组: [4, 10, 3, 5, 1]
建最大堆:
       10
      /  \
     5    3
    / \
   4   1
堆顶与末尾交换，缩小堆:
交换 10↔1 → [1,5,3,4,10] → 堆化 → [1,5,3,4][10]
交换 5↔1  → [1,4,3,5,10] → 堆化 → [1,4,3][5,10]
交换 4↔3  → [3,1,4,5,10] → 堆化 → [3,1][4,5,10]
交换 3↔1  → [1,3,4,5,10] 完成

2.8 计数排序

统计每个元素出现的次数，然后根据计数直接确定元素的位置。要求元素为整数且范围有限。时间复杂度$O(n+k)$，稳定

def counting_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    min_val = min(arr)
    range_len = max_val - min_val + 1
    count = [0] * range_len
    output = [0] * len(arr)

    for num in arr:
        count[num - min_val] += 1

    for i in range(1, len(count)):
        count[i] += count[i - 1]

    for num in reversed(arr):
        idx = count[num - min_val] - 1
        output[idx] = num
        count[num - min_val] -= 1

    return output

输入: [4, 2, 2, 8, 3, 3, 1]
范围: 1~8, 建立计数数组 count[0...7]

计数:
值  1 2 3 4 5 6 7 8
次数 1 2 2 1 0 0 0 1
累加计数:
值  1 2 3 4 5 6 7 8
累计 1 3 5 6 6 6 6 7

反向遍历原数组, 放置:
8 → 累计[8]-1=6 → output[6]=8
3 → 累计[3]-1=4 → output[4]=3
3 → 累计[3]-1=4 此时[4]已被占用就-1 → output[3]=3
1 → 累计[1]-1=0 → output[0]=1
2 → 累计[2]-1=2 → output[2]=2
2 → 累计[2]-1=2 此时[2]已被占用就-1 → output[1]=2
4 → 累计[4]-1=5 → output[5]=4
结果（output）: [1,2,2,3,3,4,8]

2.9 基数排序

按数字的每一位（个位、十位、百位等）进行多次排序，从最低位到最高位依次处理。适用于整数或定长字符串，时间复杂度$O(d*(n+k))$，稳定

def radix_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1

    for i in range(n):
        arr[i] = output[i]

输入: [170, 45, 75, 90, 802, 24, 2, 66]
按个位排序 (exp=1):
  170(0), 90(0), 802(2), 24(4), 45(5), 75(5), 66(6), 2(2)
  → 结果: [170, 90, 802, 2, 24, 45, 75, 66]
按十位排序 (exp=10):
  170(7), 90(9), 802(0), 2(0), 24(2), 45(4), 75(7), 66(6)
  → 结果: [802, 2, 24, 45, 66, 170, 75, 90]
按百位排序 (exp=100):
  802(8), 2(0), 24(0), 45(0), 66(0), 170(1), 75(0), 90(0)
  → 结果: [2, 24, 45, 66, 75, 90, 170, 802]

---

解决思路

1 暴力法

1.1 基本思路

通过嵌套循环遍历所有可能的两两组合，检查其和是否为目标值，复杂度为$O(n^2)$

1.2 具体实现

def two_sum_brute_force(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []  # 无解

2 哈希表法

2.1 基本思路

利用 Python 字典存储已遍历的数值及其下标。在遍历过程中，计算当前数值的补数（complement = target - num），并检查该补数是否已存在于哈希表中，从而将查找效率提升至$O(1)$

2.2 具体实现

def two_sum_hash_table(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]
        # 在哈希表建立过程中，检查补数是否存在于之前的 Hashing 中
        num_to_index[num] = i 
    return []  # 无解

enumerate()是 Python 的一个内置函数，主要用于在遍历列表（数组）时同时获取元素的索引（下标）和数值

3 排序+双指针

3.1 基本思路

先对数组进行排序，然后使用左右两个指针向中间移动，根据当前和的大小决定移动哪一个指针，复杂度由更大的排序决定，为$O(nlogn)$

3.2 具体实现

def two_sum_two_pointers(nums, target):
    # 存储原始下标，以便排序后能找回位置
    indexed_nums = [(num, i) for i, num in enumerate(nums)]
    indexed_nums.sort()  # 按数值排序
    
    left, right = 0, len(indexed_nums) - 1
    while left < right: # left、right是元组列表的索引
        num_left, idx_left = indexed_nums[left]
        num_right, idx_right = indexed_nums[right]
        current_sum = num_left + num_right
        
        if current_sum == target:
            return [idx_left, idx_right]
        elif current_sum < target:
            left += 1  # 当前和太小，左指针右移
        else:
            right -= 1  # 当前和太大，右指针左移
    return []  # 无解

元组(num,i)把原数值和原索引绑定,return [idx_left, idx_right]返回的就是排序前的索引

---

总结与对比

1 算法核心思路简介

• 暴力法：采用嵌套循环，遍历数组中所有可能的两两组合来寻找目标值。其逻辑最为直接，是解决问题的基础范式。
• 哈希表法：利用 Python字典作为内存中的哈希表。在遍历数组的同时，将数值映射为索引，通过平均时间复杂度为 $O(1)$ 的搜索操作快速定位补数。
• 排序+双指针法：先将数值与原始下标绑定并进行排序，随后使用左右指针向中间逼近。它是排序算法在实际检索问题中的典型应用。

2 算法复杂度对比

维度	暴力法	哈希表法	排序 + 双指针	备注
时间复杂度	$O(n^2)$	$O(n)$ (平均)	$O(nlogn)$	哈希表法在搜索效率上具有压倒性优势
空间复杂度	$O(1)$	$O(n)$	$O(n)$	暴力法不需要额外空间，而后两者需要存储哈希表或下标副本
编程难度	低	中	中	暴力法逻辑最简单；哈希法涉及哈希原理；排序法涉及下标绑定。
稳定性	高	受哈希函数影响	受排序算法影响	若哈希函数设计不佳，哈希法可能退化至 $O(n^2)$

3 算法复杂度详解

3.1 时间复杂度

• 暴力法由于需要进行 $n(n-1)/2$ 次比较，处理大规模数据（如 $n=5000$）时效率极低
• 哈希法在于将搜索操作从 $O(n)$ 降到了平均$O(1)$。总共遍历一次数组并进行 $n$ 次查找，总时间复杂度为 $O(n)$
• 双指针法的效率瓶颈在于排序步骤，其时间复杂度为 $O(nlogn)$，之后的指针移动仅需 $O(n)$

3.2 空间复杂度(以空间换时间)

• 暴力法是原地操作，不需要额外内存
• 哈希法需要一个字典来存储所有已遍历的数字及其索引，空间消耗随数据量线性增长
• 双指针法在实现中创建了 indexed_nums 列表来保存 (数值, 原始下标)，因此也产生了 $O(n)$ 的空间开销

3.3 适用场景与局限性

• 哈希法：最推荐的通用解法，尤其适用于需要极速查找的场景。但需注意冲突（Collision）处理
• 双指针法：当输入数据已经排好序时，该方法不需要额外的排序开销，空间效率可能提升至 $O(1)$
• 暴力法：仅适用于数据量极小（如 $n < 100$）且对额外空间极其敏感的环境

4. 使用场景简析

基于性能与复杂度的平衡，建议：

• 首选哈希表法：在大多数实际编程面试或应用中，为了追求最优的时间复杂度 $O(n)$，哈希法是最佳选择
• 特定场景用双指针：如果处理的是有序数组，或者内存极度受限且不允许使用哈希表，双指针法是极佳的替代方案
• 避免使用暴力法：除非是在教学场景下理解最简单的算法逻辑，否则在处理真实业务数据时应尽量避免使用嵌套循环