ARTICLE DETAIL

资讯详情

深耕网站建设与运营推广的一线实战洞察。

AlgoNote 算法通关手册:LeetCode 0001 两数之和(Two Sum)双解法全解析——从暴力枚举到哈希表

AlgoNote 算法通关手册:LeetCode 0001 两数之和(Two Sum)双解法全解析——从暴力枚举到哈希表 教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇以「算法通关手册AlgoNote」题解库中的 0001. 两数之和题解 为骨架系统拆解这道 LeetCode 入门经典题的两种解法$O(n^2)$ 暴力枚举与 $O(n)$ 哈希表查找并结合仓库中的 哈希表基础教程、数组基础教程 以及 三数之和、两数之和 II有序数组 等关联题解把「两数之和」背后的数组遍历、哈希映射、时间空间权衡等核心知识点一次讲透。读完本文你将掌握该题两种解法的手写实现、复杂度推导、边界条件处理以及如何把同一套思路迁移到有序数组与三数之和等进阶题目上。一、题目概述1.1 题目大意题目描述给定一个整数数组nums和一个整数目标值target。题目要求在该数组中找出和为target的两个整数并输出这两个整数的下标。可以按任意顺序返回答案。示例 1输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2输入nums [3,2,4], target 6 输出[1,2]1.2 数据范围与隐含条件$2 \le nums.length \le 10^4$数组长度至少为 2一定存在两个数可供组合。$-10^9 \le nums[i] \le 10^9$$-10^9 \le target \le 10^9$数值可达十亿量级但 Python 整数无溢出问题。只会存在一个有效答案——这是该题的关键简化条件意味着找到一组解即可立即返回无需考虑多解去重问题。nums[i]、target的取值范围决定了即使在哈希表解法中直接用数值本身作为字典的键也不会遇到精度问题同时数组最长可达 $10^4$暴力解法在最坏情况下需要约 $5 \times 10^7$ 次比较在 LeetCode 评测环境下通常可以接受但不够优雅。二、思路 1暴力枚举两重循环2.1 算法步骤使用两重循环枚举数组中每一个数nums[i]、nums[j]判断所有的nums[i] nums[j]是否等于target。如果出现nums[i] nums[j] target则说明数组中存在和为target的两个整数将两个整数的下标i、j输出即可。这里有一个容易踩的细节外层循环固定i后内层循环只需要从i 1开始枚举就能保证i ! j同时避免(i, j)与(j, i)的重复组合。事实上由于题目保证两个数来自不同下标i ! j的判断是冗余的——内层从i 1起步已经天然满足该条件。2.2 参考代码class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: for i in range(len(nums)): for j in range(i 1, len(nums)): if i ! j and nums[i] nums[j] target: return [i, j] return []2.3 复杂度分析时间复杂度$O(n^2)$其中 $n$ 是数组nums的元素数量。外层循环 $n$ 次内层循环平均约 $n/2$ 次总比较次数约为 $n(n-1)/2$。空间复杂度$O(1)$只使用了常数级别的额外变量。2.4 与数组基础知识的关联暴力枚举之所以可行依赖于数组「支持按下标随机访问」的特性。仓库的 数组基础教程 中明确指出数组是一段连续的内存空间可通过「首地址 下标 × 元素大小」的寻址公式在 $O(1)$ 时间内定位任意元素因此nums[i]的每次访问都是常数时间而「线性查找一个不存在的元素」则需要遍历全部元素时间复杂度为 $O(n)$——这正是本题暴力解法退化为 $O(n^2)$ 的根因$n$ 个候选nums[i]每个都要做一次 $O(n)$ 的线性查找。三、思路 2哈希表一次遍历3.1 核心思想空间换时间暴力解法慢在「查找补数」这一步是线性扫描。如果我们能像查字典一样通过「键」直接定位到「值」就能把查找补数的时间从 $O(n)$ 降到 $O(1)$。这正是哈希表Hash Table的用武之地。仓库的 哈希表基础教程 对哈希表给出了精确定义哈希表Hash Table又称散列表是一种能通过关键码Key直接访问数据的结构。哈希表利用「键key」和「哈希函数Hash(key)」将关键码映射到表中的某个位置从而实现高效的查找和存储。在 Python 中字典dict就是哈希表的典型实现其底层通过哈希函数将键映射到桶bucket位置插入与查找的平均时间复杂度均为 $O(1)$。3.2 算法步骤哈希表中键值对信息为target - nums[i] : i其中i为下标。遍历数组对于每一个数nums[i]先查找字典中是否存在target - nums[i]存在则输出target - nums[i]对应的下标和当前数组的下标i不存在则在字典中存入target - nums[i]的下标i。3.3 参考代码def twoSum(self, nums: List[int], target: int) - List[int]: numDict dict() for i in range(len(nums)): if target - nums[i] in numDict: return numDict[target - nums[i]], i numDict[nums[i]] i return [0]3.4 逐步推演以示例 1 为例给定nums [2,7,11,15], target 9步骤inums[i]字典中存在target - nums[i]操作字典状态1027不存在存入2 - 0{2: 0}2172存在下标 0返回[0, 1]—可以看到一次遍历即可完成查找字典保存的是「已经扫过」的每个数的下标未来某个数恰好是某个已扫过数的补数时就能立刻命中。这也解释了为什么要把nums[i]而不是target - nums[i]作为键存入——存入已见元素才能支持「补数匹配」的语义。3.5 复杂度分析时间复杂度$O(n)$其中 $n$ 是数组nums的元素数量。每个元素只需一次字典插入和一次字典查询而 Python 字典的插入与查询平均复杂度均为 $O(1)$。空间复杂度$O(n)$最坏情况下答案在数组末尾或不存在需要把全部 $n$ 个元素存入字典。3.6 边界条件与细节讨论答案存在性题目保证「只会存在一个有效答案」因此遍历过程中必然命中并提前返回。若题目不保证存在答案则应在循环结束后返回空结果如[-1, -1]或[]原题解末尾的return [0]属于不可达的兜底代码。相同元素处理当数组中出现重复元素例如nums [3,3], target 6时遍历到第二个3时字典中已经存有第一个3的下标0target - 3 3命中返回[0, 1]正确。关键在于「先查后存」的顺序若先存入再查询第二个3会直接覆盖第一个3的下标导致答案丢失。因此「先查再存」的顺序不可颠倒。为什么不用nums[i]查补数若先遍历一遍把全部nums[i] - i存入字典再二次遍历查找补数会引入「同一个元素被使用两次」的误判如nums [3,2,4], target 6时3的补数3恰好是它自己需要额外的i ! j判断。单次遍历的「边查边存」写法天然规避了该问题。3.7 哈希表原理的纵深补充从源码结构看本题的哈希表解法是 哈希表基础教程 中「哈希表原理示意」章节的工程化落地哈希函数Python 字典内部对整数键调用哈希函数如除留余数法 $Hash(key) key \mod p$ 的变体计算桶位置本题以nums[i]为键哈希计算本身是常数时间哈希冲突现实中不同键可能映射到同一地址如 $key1 \ne key2$ 但 $Hash(key1) Hash(key2)$Python 字典采用开放寻址策略解决冲突。冲突的存在使得字典操作的最坏时间复杂度退化为 $O(n)$但平均情况下仍为 $O(1)$——因此上述复杂度分析中「$O(1)$ 查询」的前提是哈希函数分布均匀在实际评测数据中该前提成立空间开销哈希表需要为存储键值对分配额外内存这正是与暴力解法相比「用 $O(n)$ 空间换取从 $O(n^2)$ 到 $O(n)$ 的时间」的根本取舍。四、两种思路对比与选型建议维度思路 1暴力枚举思路 2哈希表核心思想两重循环穷举所有下标组合用字典记录已见元素一次遍历查补数时间复杂度$O(n^2)$$O(n)$空间复杂度$O(1)$$O(n)$实现难度极低两层循环即可低但需注意「先查后存」的顺序适用场景数据量极小、或禁止额外空间常规刷题与面试的首选方案选型建议工程与面试场景下优先使用哈希表解法——它既是最优时间复杂度的代表也是「空间换时间」思想的入门范例暴力枚举的价值则在于帮助理解数组遍历与组合枚举的基本功。若数组长度增长到 $10^5$ 甚至 $10^6$ 量级暴力解法将不可接受哈希表是唯一实用选择。五、同族题型的迁移拓展「两数之和」是众多数组求和问题的基石仓库题解库中围绕它衍生出一系列变体掌握思路迁移比背代码更有价值。5.1 两数之和 II输入有序数组LeetCode 0167当数组升序排列时可以抛弃哈希表改用对撞指针左指针left指向最小值位置下标 0右指针right指向最大值位置末尾计算numbers[left] numbers[right]与target的关系和等于target返回两个位置注意该题下标从 1 开始计数和大于targetright左移减小总和和小于targetleft右移增大总和。class Solution: def twoSum(self, numbers: List[int], target: int) - List[int]: left 0 right len(numbers) - 1 while left right: total numbers[left] numbers[right] if total target: return [left 1, right 1] elif total target: left 1 else: right - 1 return [-1, -1]该解法时间复杂度 $O(n)$、空间复杂度 $O(1)$详细推导见 两数之和 II - 输入有序数组题解。注意本题的left 1与right - 1移动策略依赖数组的有序性若无序数组不能直接套用对撞指针。5.2 三数之和LeetCode 0015从「两个数」升级到「三个数」且要求结果三元组不重复解法升级为「排序 对撞指针」先将数组排序保证枚举过程有序、便于去重第一重循环固定nums[i]用对撞指针在i之后寻找nums[left] nums[right] -nums[i]遇到相邻重复元素时跳过如nums[i] nums[i-1]时continue避免重复三元组。完整实现与复杂度分析$O(n^2)$ 时间、$O(n)$ 空间见 三数之和题解。三数之和的「排序预处理」思路正是两数之和在有序场景下对撞指针解法的直接延伸。5.3 其他相关题目四数之和LeetCode 0018「排序 双重循环 对撞指针」把三数之和再嵌套一层存在重复元素LeetCode 0217利用哈希表判重是「用哈希表加速查询」思路的另一典型应用两数之和 III - 数据结构设计LeetCode 0170把查询操作封装进类考察哈希表在动态数据集上的应用。仓库的 分类题目列表 按「数组」「哈希表」「双指针」等标签对全部题解做了归类可在对应分类下找到上述全部题目的完整解析。六、总结两数之和LeetCode 0001虽然难度标记为「简单」却同时承载了三个重要知识点数组遍历基于连续内存的随机访问特性见 数组基础教程让nums[i]的访问是 $O(1)$ 的哈希表利用「键值对直接寻址」将补数查询从 $O(n)$ 降到 $O(1)$见 哈希表基础教程体现了「空间换时间」的经典权衡算法思维进阶从暴力枚举到哈希表的优化过程是理解「如何降低时间复杂度」的标准范式其变体有序数组对撞指针、三数之和排序去重贯穿整个算法面试体系。在「算法通关手册AlgoNote」的学习路径中本题作为 0001-0099 题解区间 的开篇题目建议读者在掌握本文两种解法后顺手完成 两数之和 II 与 三数之和 的练习即可完成「两数之和」知识点族的闭环。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode Two Integer Sum两数之和解法全解从暴力枚举到 O(n) 哈希表单遍扫描LeetCode Two Integer Sum两数之和解法全解从暴力枚举到 O n 哈希表单遍扫描 导读 本文以本仓库 hints/two intege示例工程教程LeetCode-Go 题解精讲0001.Two Sum 两数之和O(n) 哈希表解法与测试验证LeetCode Go 题解精讲0001.Two Sum 两数之和O n 哈希表解法与测试验证 本篇技术指南以 LeetCode Go 仓库中 0001.示例工程LeetCode-Go 题解精讲0001. Two Sum 两数之和的 O(n) 哈希解法与源码剖析LeetCode Go 题解精讲0001. Two Sum 两数之和的 O n 哈希解法与源码剖析 导读 本文以 LeetCode 第 1 题 Two Sum示例工程上一篇NGT高性能高维数据近邻搜索的终极解决方案下一篇eSearch终极使用指南释放屏幕生产力的10个秘诀创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表