LeetCode 两数之和 思路 + 题解

好的我们来详细分析LeetCode 两数之和题目编号1的解题思路并提供代码实现。问题描述给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。假设每种输入只会对应一个答案且数组中同一个元素不能使用两次。示例输入nums [2,7,11,15], target 9 输出[0,1]思路分析1.暴力枚举法不推荐思路遍历数组中每一个元素nums[i]对每个元素再遍历其后的元素nums[j]检查是否满足 $$ \text{nums}[i] \text{nums}[j] \text{target} $$。时间复杂度$$ O(n^2) $$缺点当数组较大时效率极低。2.哈希表优化法推荐核心思路利用哈希表存储值→索引的映射实现 $$ O(1) $$ 的查找效率。步骤创建一个空字典num_map键为数值值为索引。遍历数组对于当前元素nums[i]计算互补数 $$ \text{complement} \text{target} - \text{nums}[i] $$。检查complement是否在num_map中若存在则返回[num_map[complement], i]。若不存在则将nums[i]和索引i存入字典。时间复杂度$$ O(n) $$空间复杂度$$ O(n) $$哈希表开销代码实现Python 版本def twoSum(nums, target): num_map {} for i, num in enumerate(nums): complement target - num if complement in num_map: return [num_map[complement], i] num_map[num] i return [] # 题目保证有解实际可省略Go 版本func twoSum(nums []int, target int) []int { numMap : make(map[int]int) for i, num : range nums { complement : target - num if idx, ok : numMap[complement]; ok { return []int{idx, i} } numMap[num] i } return nil }关键点总结哈希表加速查找通过空间换时间将查找互补数的时间复杂度降至 $$ O(1) $$。边遍历边存储避免重复处理同一元素如先存整个数组再查找会无法区分相同值。处理重复值题目允许不同索引的相同值如[3,3], target6但哈希表会覆盖旧索引由于遍历顺序新索引被存储时旧索引已参与过匹配故不影响结果。测试用例验证用例1nums [2,7,11,15], target 9→ 输出[0,1]用例2nums [3,2,4], target 6→ 输出[1,2]用例3nums [3,3], target 6→ 输出[0,1]此解法高效且通用是面试中的标准答案。