 降到 O(n))
Hello 算法两数之和中的哈希优化策略——如何用空间换时间将查找从 O(n²) 降到 O(n)【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo在算法题中我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。《Hello 算法》在 replace_linear_by_hashing.md 一节中以经典的两数之和Two Sum问题为例系统演示了这一优化思想的完整推导过程。读完本文你将掌握暴力枚举与哈希查找两种解法的代码实现、复杂度分析以及为什么空间换时间是本题的最优解并能将这一策略迁移到其他查找类问题中。问题定义在数组中搜索和为 target 的两个元素!!! question给定一个整数数组 nums 和一个目标元素 target 请在数组中搜索和为 target 的两个元素并返回它们的数组索引。返回任意一个解即可。该问题的输入输出约定如下输入整数数组nums与目标值target输出两个元素的数组索引[i, j]满足nums[i] nums[j] target约束返回任意一个解即可不需要枚举全部组合。以仓库测试用例为例如 two_sum.c 中的 Driver Code给定nums [2, 7, 11, 15]、target 13答案为索引[0, 2]因为2 11 13。线性查找以时间换空间考虑直接遍历所有可能的组合。如下图所示我们开启一个两层循环在每轮中判断两个整数的和是否为target若是则返回它们的索引。外层循环固定第一个元素nums[i]内层循环从i 1开始扫描后续元素nums[j]逐一检查nums[i] nums[j] target。之所以从i 1开始是因为无序对(i, j)与(j, i)等价避免重复计算同时任何元素都不可能与自身配对除非题目另有说明允许使用同一元素两次。多语言实现暴力枚举Python 实现见 two_sum.pydef 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]; }C 语言实现见 two_sum.c需额外借助returnSize指针向调用方传递结果长度C 实现见 two_sum.cpp使用vectorint返回Go 实现见 two_sum.go。各语言实现逻辑完全一致仅在语法与返回机制上有所差异。复杂度分析O(n²) 时间的代价时间复杂度为 $O(n^2)$外层循环执行 $n$ 次内层循环平均执行约 $n/2$ 次总比较次数约为 $n(n-1)/2$随数据规模平方增长空间复杂度为 $O(1)$只使用了常数个临时变量没有额外分配与输入规模相关的存储。此方法在大数据量下非常耗时。当 $n 10^4$ 时需执行约 $5 \times 10^7$ 次比较当 $n 10^6$ 时更达到约 $5 \times 10^{11}$ 次这在多数在线评测与生产场景中都是不可接受的。暴力枚举的瓶颈在于每检查一个nums[i]都要花费 $O(n)$ 时间去线性扫描另一半而哈希表恰好在这一点上提供 $O(1)$ 的查找能力。哈希查找以空间换时间考虑借助一个哈希表键值对分别为数组元素和元素索引。循环遍历数组每轮执行下图所示的步骤判断数字target - nums[i]是否在哈希表中若是则直接返回这两个元素的索引将键值对nums[i]和索引i添加进哈希表。整个过程的运行逻辑可以这样理解遍历到元素nums[i]时它的另一半必然是target - nums[i]。如果这一半在之前已经出现过那么它一定已经作为键存入了哈希表只需 $O(1)$ 即可命中如果尚未出现就把当前元素连同索引存入哈希表供后续元素查询。这种边走边存、边查边回的方式保证每个元素最多被查询与插入各一次。关键技巧在于先查后插的顺序每轮先查询target - nums[i]是否已在表中再插入nums[i]。这样保证了查询到的配对元素必然位于当前元素之前索引更小返回结果[表中索引, i]的先后顺序是确定且正确的。同时也天然规避了元素与自身配对的问题——因为当前元素尚未插入查询不可能命中它自己。多语言实现辅助哈希表Python 实现见 two_sum.pydef 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使用HashMapInteger, Integer键为元素值、值为索引/* 方法二辅助哈希表 */ static int[] twoSumHashTable(int[] nums, int target) { int size nums.length; // 辅助哈希表空间复杂度为 O(n) MapInteger, 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 实现见 two_sum.go直接使用内建map[int]int并以ok布尔值判断键是否存在/* 方法二辅助哈希表 */ 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 }C 语言实现基于 uthash 的手写哈希表C 语言没有内建哈希表仓库实现借助开源库uthash完成了同样的逻辑。相关代码见 two_sum.c包括三个组成部分表结构定义以int key存元素值、int val存索引并内嵌UT_hash_handle hh宏字段uthash 要求每个表节点都必须包含该句柄查询函数find通过HASH_FIND_INT(h, key, tmp)按整数键查找插入函数insert先查重键不存在时HASH_ADD_INT新增节点存在时更新val防止重复元素覆盖索引。主函数twoSumHashTable的核心循环与其他语言完全同构先find(hashtable, target - nums[i])查询命中即返回[t-val, i]未命中则insert(hashtable, nums[i], i)存入当前元素。从源码结构看uthash的HASH_FIND_INT与HASH_ADD_INT内部基于哈希桶与链地址法实现平均查找/插入复杂度为 $O(1)$与本节的复杂度结论一致。这也说明哈希优化的核心是查找数据结构的升级与具体语言或库的选型无关只要能提供 $O(1)$ 平均复杂度的键值查询即可。复杂度分析O(n) 时间 O(n) 空间时间复杂度为 $O(n)$仅需单层循环遍历数组一次每轮执行一次哈希查找与一次哈希插入平均均为 $O(1)$空间复杂度为 $O(n)$需要维护一个额外的哈希表最多存储 $n$ 个键值对。该方法通过哈希查找将时间复杂度从 $O(n^2)$ 降至 $O(n)$ 大幅提升运行效率。代价是额外付出 $O(n)$ 的哈希表存储空间。时空权衡为什么哈希解法是本题的最优解将两种方法对比可以直观地看到时间换空间与空间换时间两种策略的取舍方法核心思路时间复杂度空间复杂度适用场景暴力枚举两层循环遍历所有组合$O(n^2)$$O(1)$数据规模极小、对内存极敏感辅助哈希表单层循环 $O(1)$ 哈希查找$O(n)$$O(n)$数据规模较大、追求运行效率暴力枚举省下了哈希表的空间却把时间拖到了平方级哈希解法付出 $O(n)$ 的额外空间换来的是从 $O(n^2)$ 到 $O(n)$ 的量级跃迁。由于需要维护一个额外的哈希表因此空间复杂度为 $O(n)$。尽管如此该方法的整体时空效率更为均衡因此它是本题的最优解法。这一判断的深层原因在于本题任意返回一个解的要求给了算法极大的自由度——不需要排序排序至少是 $O(n \log n)$、不需要记录全部组合只需要在遍历过程中记住已经见过的元素即可。哈希表恰好以 $O(1)$ 的读写成本完成这一记忆任务使总复杂度线性可解。需要说明的适用前提与限制哈希表平均 $O(1)$ 的查找复杂度依赖于良好的散列函数与足够的桶容量在极端哈希冲突场景下可能退化但工程实践中如 JavaHashMap、Gomap、uthash均有扩容与冲突处理机制可视为平均 $O(1)$当数组规模 $n$ 很小时哈希表的常数开销可能使其未必明显快于暴力枚举但从渐近复杂度看前者仍具优势若题目要求返回所有满足条件的组合则问题退化为组合枚举问题哈希策略只适用于求是否存在/返回任意一组的变体不可盲目套用。策略迁移把线性查找替换为哈希查找推广到更多问题本节方法论的价值不止于一道两数之和它总结出一个可复用的优化范式识别线性扫描的瓶颈当内层循环反复在数据集中做是否存在某元素的查询时就存在替换为哈希查找的空间用哈希表缓存已见信息以查询所需的键为哈希键以需要回传的值为哈希值保持单次遍历查询与写入在同一次遍历中交替完成避免二次扫描。这一范式在《Hello 算法》的后续章节中有多处呼应例如 哈希表章节 详细讲解了哈希表的底层原理与冲突处理查找章节 将各查找算法放在一起比较其适用场景在 時間複雜度章節 中你可以进一步理解 $O(n^2)$ 与 $O(n)$ 在数据规模增长时的巨大差异。本文的两数之和正是用哈希优化查找最简洁、最典型的入门案例。快速验证运行仓库源码查看两种解法的输出仓库为两种方法都提供了完整的 Driver Code 测试用例统一使用nums [2, 7, 11, 15]、target 13可以直接运行验证# Python 版本输出方法一 res [0, 2]方法二 res [0, 2] python3 codes/python/chapter_searching/two_sum.py # Java 版本需先编译 cd codes/java javac chapter_searching/two_sum.java java chapter_searching.two_sumC 语言版本使用 CMake 构建构建入口见 codes/c/CMakeLists.txtC 版本的 Driver Code 见 two_sum.cpp。你可以修改测试用例中的nums与target亲身体验当数组规模变大时暴力枚举的耗时增长远快于哈希解法——这正是从 $O(n^2)$ 到 $O(n)$ 的直观印证。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法：两数之和中的哈希优化策略——如何用空间换时间将查找从 O(n²) 降到 O(n)
Hello 算法两数之和中的哈希优化策略——如何用空间换时间将查找从 O(n²) 降到 O(n)【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo在算法题中我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。《Hello 算法》在 replace_linear_by_hashing.md 一节中以经典的两数之和Two Sum问题为例系统演示了这一优化思想的完整推导过程。读完本文你将掌握暴力枚举与哈希查找两种解法的代码实现、复杂度分析以及为什么空间换时间是本题的最优解并能将这一策略迁移到其他查找类问题中。问题定义在数组中搜索和为 target 的两个元素!!! question给定一个整数数组 nums 和一个目标元素 target 请在数组中搜索和为 target 的两个元素并返回它们的数组索引。返回任意一个解即可。该问题的输入输出约定如下输入整数数组nums与目标值target输出两个元素的数组索引[i, j]满足nums[i] nums[j] target约束返回任意一个解即可不需要枚举全部组合。以仓库测试用例为例如 two_sum.c 中的 Driver Code给定nums [2, 7, 11, 15]、target 13答案为索引[0, 2]因为2 11 13。线性查找以时间换空间考虑直接遍历所有可能的组合。如下图所示我们开启一个两层循环在每轮中判断两个整数的和是否为target若是则返回它们的索引。外层循环固定第一个元素nums[i]内层循环从i 1开始扫描后续元素nums[j]逐一检查nums[i] nums[j] target。之所以从i 1开始是因为无序对(i, j)与(j, i)等价避免重复计算同时任何元素都不可能与自身配对除非题目另有说明允许使用同一元素两次。多语言实现暴力枚举Python 实现见 two_sum.pydef 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]; }C 语言实现见 two_sum.c需额外借助returnSize指针向调用方传递结果长度C 实现见 two_sum.cpp使用vectorint返回Go 实现见 two_sum.go。各语言实现逻辑完全一致仅在语法与返回机制上有所差异。复杂度分析O(n²) 时间的代价时间复杂度为 $O(n^2)$外层循环执行 $n$ 次内层循环平均执行约 $n/2$ 次总比较次数约为 $n(n-1)/2$随数据规模平方增长空间复杂度为 $O(1)$只使用了常数个临时变量没有额外分配与输入规模相关的存储。此方法在大数据量下非常耗时。当 $n 10^4$ 时需执行约 $5 \times 10^7$ 次比较当 $n 10^6$ 时更达到约 $5 \times 10^{11}$ 次这在多数在线评测与生产场景中都是不可接受的。暴力枚举的瓶颈在于每检查一个nums[i]都要花费 $O(n)$ 时间去线性扫描另一半而哈希表恰好在这一点上提供 $O(1)$ 的查找能力。哈希查找以空间换时间考虑借助一个哈希表键值对分别为数组元素和元素索引。循环遍历数组每轮执行下图所示的步骤判断数字target - nums[i]是否在哈希表中若是则直接返回这两个元素的索引将键值对nums[i]和索引i添加进哈希表。整个过程的运行逻辑可以这样理解遍历到元素nums[i]时它的另一半必然是target - nums[i]。如果这一半在之前已经出现过那么它一定已经作为键存入了哈希表只需 $O(1)$ 即可命中如果尚未出现就把当前元素连同索引存入哈希表供后续元素查询。这种边走边存、边查边回的方式保证每个元素最多被查询与插入各一次。关键技巧在于先查后插的顺序每轮先查询target - nums[i]是否已在表中再插入nums[i]。这样保证了查询到的配对元素必然位于当前元素之前索引更小返回结果[表中索引, i]的先后顺序是确定且正确的。同时也天然规避了元素与自身配对的问题——因为当前元素尚未插入查询不可能命中它自己。多语言实现辅助哈希表Python 实现见 two_sum.pydef 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使用HashMapInteger, Integer键为元素值、值为索引/* 方法二辅助哈希表 */ static int[] twoSumHashTable(int[] nums, int target) { int size nums.length; // 辅助哈希表空间复杂度为 O(n) MapInteger, 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 实现见 two_sum.go直接使用内建map[int]int并以ok布尔值判断键是否存在/* 方法二辅助哈希表 */ 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 }C 语言实现基于 uthash 的手写哈希表C 语言没有内建哈希表仓库实现借助开源库uthash完成了同样的逻辑。相关代码见 two_sum.c包括三个组成部分表结构定义以int key存元素值、int val存索引并内嵌UT_hash_handle hh宏字段uthash 要求每个表节点都必须包含该句柄查询函数find通过HASH_FIND_INT(h, key, tmp)按整数键查找插入函数insert先查重键不存在时HASH_ADD_INT新增节点存在时更新val防止重复元素覆盖索引。主函数twoSumHashTable的核心循环与其他语言完全同构先find(hashtable, target - nums[i])查询命中即返回[t-val, i]未命中则insert(hashtable, nums[i], i)存入当前元素。从源码结构看uthash的HASH_FIND_INT与HASH_ADD_INT内部基于哈希桶与链地址法实现平均查找/插入复杂度为 $O(1)$与本节的复杂度结论一致。这也说明哈希优化的核心是查找数据结构的升级与具体语言或库的选型无关只要能提供 $O(1)$ 平均复杂度的键值查询即可。复杂度分析O(n) 时间 O(n) 空间时间复杂度为 $O(n)$仅需单层循环遍历数组一次每轮执行一次哈希查找与一次哈希插入平均均为 $O(1)$空间复杂度为 $O(n)$需要维护一个额外的哈希表最多存储 $n$ 个键值对。该方法通过哈希查找将时间复杂度从 $O(n^2)$ 降至 $O(n)$ 大幅提升运行效率。代价是额外付出 $O(n)$ 的哈希表存储空间。时空权衡为什么哈希解法是本题的最优解将两种方法对比可以直观地看到时间换空间与空间换时间两种策略的取舍方法核心思路时间复杂度空间复杂度适用场景暴力枚举两层循环遍历所有组合$O(n^2)$$O(1)$数据规模极小、对内存极敏感辅助哈希表单层循环 $O(1)$ 哈希查找$O(n)$$O(n)$数据规模较大、追求运行效率暴力枚举省下了哈希表的空间却把时间拖到了平方级哈希解法付出 $O(n)$ 的额外空间换来的是从 $O(n^2)$ 到 $O(n)$ 的量级跃迁。由于需要维护一个额外的哈希表因此空间复杂度为 $O(n)$。尽管如此该方法的整体时空效率更为均衡因此它是本题的最优解法。这一判断的深层原因在于本题任意返回一个解的要求给了算法极大的自由度——不需要排序排序至少是 $O(n \log n)$、不需要记录全部组合只需要在遍历过程中记住已经见过的元素即可。哈希表恰好以 $O(1)$ 的读写成本完成这一记忆任务使总复杂度线性可解。需要说明的适用前提与限制哈希表平均 $O(1)$ 的查找复杂度依赖于良好的散列函数与足够的桶容量在极端哈希冲突场景下可能退化但工程实践中如 JavaHashMap、Gomap、uthash均有扩容与冲突处理机制可视为平均 $O(1)$当数组规模 $n$ 很小时哈希表的常数开销可能使其未必明显快于暴力枚举但从渐近复杂度看前者仍具优势若题目要求返回所有满足条件的组合则问题退化为组合枚举问题哈希策略只适用于求是否存在/返回任意一组的变体不可盲目套用。策略迁移把线性查找替换为哈希查找推广到更多问题本节方法论的价值不止于一道两数之和它总结出一个可复用的优化范式识别线性扫描的瓶颈当内层循环反复在数据集中做是否存在某元素的查询时就存在替换为哈希查找的空间用哈希表缓存已见信息以查询所需的键为哈希键以需要回传的值为哈希值保持单次遍历查询与写入在同一次遍历中交替完成避免二次扫描。这一范式在《Hello 算法》的后续章节中有多处呼应例如 哈希表章节 详细讲解了哈希表的底层原理与冲突处理查找章节 将各查找算法放在一起比较其适用场景在 時間複雜度章節 中你可以进一步理解 $O(n^2)$ 与 $O(n)$ 在数据规模增长时的巨大差异。本文的两数之和正是用哈希优化查找最简洁、最典型的入门案例。快速验证运行仓库源码查看两种解法的输出仓库为两种方法都提供了完整的 Driver Code 测试用例统一使用nums [2, 7, 11, 15]、target 13可以直接运行验证# Python 版本输出方法一 res [0, 2]方法二 res [0, 2] python3 codes/python/chapter_searching/two_sum.py # Java 版本需先编译 cd codes/java javac chapter_searching/two_sum.java java chapter_searching.two_sumC 语言版本使用 CMake 构建构建入口见 codes/c/CMakeLists.txtC 版本的 Driver Code 见 two_sum.cpp。你可以修改测试用例中的nums与target亲身体验当数组规模变大时暴力枚举的耗时增长远快于哈希解法——这正是从 $O(n^2)$ 到 $O(n)$ 的直观印证。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考