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) $$ 的查找效率。
• 步骤：
  1. 创建一个空字典num_map（键为数值，值为索引）。
  2. 遍历数组，对于当前元素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 }

关键点总结

1. 哈希表加速查找：通过空间换时间，将查找互补数的时间复杂度降至 $$ O(1) $$。
2. 边遍历边存储：避免重复处理同一元素（如先存整个数组再查找会无法区分相同值）。
3. 处理重复值：题目允许不同索引的相同值（如[3,3], target=6），但哈希表会覆盖旧索引，由于遍历顺序，新索引被存储时旧索引已参与过匹配，故不影响结果。

测试用例验证

• 用例1：nums = [2,7,11,15], target = 9→ 输出[0,1]
• 用例2：nums = [3,2,4], target = 6→ 输出[1,2]
• 用例3：nums = [3,3], target = 6→ 输出[0,1]

此解法高效且通用，是面试中的标准答案。