hello-algo 哈希优化策略：以空间换时间，把两数之和从 O(n²) 降到 O(n)

本篇技术指南基于《Hello 算法》搜索章节中的「哈希优化策略」文档，以经典的「两数之和」问题为主线，完整讲解如何用哈希查找替换线性查找来降低时间复杂度。读完后你将掌握暴力枚举法与辅助哈希表法两种解法的完整实现、逐步执行过程与时间空间复杂度分析，并能在 Python、Java、Go、TypeScript、C 等多语言代码中直接复用同一套思路。

问题定义：两数之和

在算法题中，我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。本文借助如下问题加深理解：

给定一个整数数组 nums 和一个目标元素 target，请在数组中搜索“和”为 target 的两个元素，并返回它们的数组索引。返回任意一个解即可。

仓库中各语言实现统一使用的测试用例为 nums = [2, 7, 11, 15]、target = 13，期望输出索引 [1, 2]（因为 7 + 11 = 13）。该用例可在此处确认：Python 驱动代码、Go 测试用例。

方法一：暴力枚举——线性查找，以时间换空间

算法思路

最直接的做法是遍历所有可能的元素组合：开启一个两层循环，在每轮中判断两个整数的和是否为 target，若是，则返回它们的索引。内层循环本质上是在「已选定 nums[i] 之后」做一遍线性查找，枚举总次数约为 n(n-1)/2。

完整实现

Python 版本完整代码如下（two_sum.py）：

def two_sum_brute_force(nums: list[int], target: int) -> list[int]:
    """方法一：暴力枚举"""
    # 两层循环，时间复杂度为 O(n^2)
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Java 版本实现等价（two_sum.java）：

/* 方法一：暴力枚举 */
static int[] twoSumBruteForce(int[] nums, int target) {
    int size = nums.length;
    // 两层循环，时间复杂度为 O(n^2)
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (nums[i] + nums[j] == target)
                return new int[] { i, j };
        }
    }
    return new int[0];
}

复杂度分析

• 时间复杂度：O(n²)，双层循环遍历所有配对；
• 空间复杂度：O(1)，仅使用常数额外空间；
• 适用性：在大数据量下非常耗时，适合数据规模小或对内存极度敏感的场景。

各语言实现遵循同一结构，可对照阅读：TypeScript 版本、C 版本。

方法二：辅助哈希表——哈希查找，以空间换时间

算法思路

借助一个哈希表，键值对分别为数组元素和元素索引。循环遍历数组，每轮执行以下两步：

1. 判断数字 target - nums[i] 是否在哈希表中，若是，则直接返回这两个元素的索引；
2. 将键值对 nums[i] 和索引 i 添加进哈希表。

这里的关键细节是**「先查找、后插入」的顺序**：因为当前元素 nums[i] 尚未写入哈希表，所以即使数组中存在重复值，查找 target - nums[i] 也不可能命中自己本身，天然避免了「同一个元素被使用两次」的非法解。

结合仓库中的图示（见文首三张步骤图），以 nums = [2, 7, 11, 15]、target = 13 为例逐步执行：

• 第 1 步：处理 nums[0] = 2，查找 13 - 2 = 11 未命中，插入 (2, 0)；
• 第 2 步：处理 nums[1] = 7，查找 13 - 7 = 6 未命中，插入 (7, 1)；
• 第 3 步：处理 nums[2] = 11，查找 13 - 11 = 2 命中，返回索引 [0, 2] 对应的配对——注意此时返回的是 [1, 2] 中先出现者索引与当前索引的组合，即 [1, 2]（7 在索引 1，11 在索引 2），7 + 11 = 13，算法结束。

完整实现

仅需单层循环即可（two_sum.py）：

def two_sum_hash_table(nums: list[int], target: int) -> list[int]:
    """方法二：辅助哈希表"""
    # 辅助哈希表，空间复杂度为 O(n)
    dic = {}
    # 单层循环，时间复杂度为 O(n)
    for i in range(len(nums)):
        if target - nums[i] in dic:
            return [dic[target - nums[i]], i]
        dic[nums[i]] = i
    return []

Java 版本（two_sum.java）：

/* 方法二：辅助哈希表 */
static int[] twoSumHashTable(int[] nums, int target) {
    int size = nums.length;
    // 辅助哈希表，空间复杂度为 O(n)
    Map<Integer, Integer> dic = new HashMap<>();
    // 单层循环，时间复杂度为 O(n)
    for (int i = 0; i < size; i++) {
        if (dic.containsKey(target - nums[i])) {
            return new int[] { dic.get(target - nums[i]), i };
        }
        dic.put(nums[i], i);
    }
    return new int[0];
}

Go 版本用 range + 双返回值判 ok 的方式完成同构逻辑（two_sum.go）：

/* 方法二：辅助哈希表 */
func twoSumHashTable(nums []int, target int) []int {
	// 辅助哈希表，空间复杂度为 O(n)
	hashTable := map[int]int{}
	// 单层循环，时间复杂度为 O(n)
	for idx, val := range nums {
		if preIdx, ok := hashTable[target-val]; ok {
			return []int{preIdx, idx}
		}
		hashTable[val] = idx
	}
	return nil
}

复杂度分析

• 时间复杂度：O(n)。单层循环遍历一次数组，每轮哈希查找与插入均为平均 O(1)，总体从暴力法的 O(n²) 降至 O(n)，大幅提升运行效率；
• 空间复杂度：O(n)，需要维护一个额外哈希表，最坏情况下存入 n 个键值对。

尽管如此，该方法的整体时空效率更为均衡，因此它是本题的最优解法。

跨语言实现细节印证

从源码结构看，各语言实现严格保持了「查找互补值 → 返回索引对 → 插入当前元素」的同一顺序，但处理哈希容器差异时各有细节：

• TypeScript 版本（two_sum.ts）使用 Map 存储，并通过 index !== undefined 判断命中。这一写法是必要的：索引 0 是合法值，若误用 if (index) 的假值判断，会漏掉命中索引为 0 的解；
• C 版本（two_sum.c）由于 C 语言没有内置哈希容器，借助仓库工具目录中的 uthash.h 宏封装了 HashTable 结构体：find() 用 HASH_FIND_INT 做查询，insert() 用 HASH_ADD_INT 做插入，语义与 Python 字典的 in / 赋值完全对应；
• Go 测试文件（two_sum_test.go）对两种方法分别调用并打印结果，是仓库内验证两种解法一致性的直接测试依据。

两种解法的对比小结

维度	暴力枚举（线性查找）	辅助哈希表（哈希查找）
时间复杂度	O(n²)	O(n)
空间复杂度	O(1)	O(n)
循环层数	双层	单层
数据结构	无	哈希表（键=元素值，值=索引）
适用场景	数据量小、内存受限	大规模数据、追求运行效率（本题最优解）

这一案例浓缩了搜索章节的核心思想：当问题中存在「查找某个值是否出现过」的子过程时，把线性查找替换为哈希查找，用 O(n) 的额外空间把整体时间从 O(n²) 降到 O(n)。同样的模式可以直接迁移到「寻找和为 k 的三数组合」「字符串异位词匹配」等需要频繁存在性判断的问题上。

延伸阅读

• 搜索章节总览：binary_search.md、searching_algorithm_revisited.md
• 本章练习题：exercises.md
• 多语言对照实现：Python、Java、Go、TypeScript、C