力扣第 1 题 — 两数之和

题目描述

来源： LeetCode 第 1 题 — 两数之和
难度： 简单

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例

示例 1：

1
2
3

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2

输入：nums = [3, 2, 4], target = 6
输出：[1, 2]

示例 3：

1
2

输入：nums = [3, 3], target = 6
输出：[0, 1]

提示

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 只会存在一个有效答案

解法一：暴力枚举（不推荐）

最直观的思路：两层循环遍历所有数对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// twoSum 暴力解法：两层循环枚举所有数对
func twoSum(nums []int, target int) []int {
	n := len(nums)
	for i := 0; i < n; i++ {
		// 从 i+1 开始，避免重复使用同一个元素
		for j := i + 1; j < n; j++ {
			// 找到和为 target 的两个数，返回下标
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}
	// 题目保证有解，这里不会执行到
	return nil
}

• 时间复杂度： O(n²) — 两层循环
• 空间复杂度： O(1)

当数组长度达到 10⁴ 时，n² = 10⁸，会超时。

解法二：哈希表（推荐 ⭐）

核心思路：边遍历边记录。对于每个数 nums[i]，检查 target - nums[i] 是否已经在哈希表中出现过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// twoSum 哈希表解法：一次遍历，O(n) 时间
func twoSum(nums []int, target int) []int {
	// map 记录「数值 → 索引」的映射
	// 初始化容量为数组长度，避免频繁扩容
	seen := make(map[int]int, len(nums))

	for i, num := range nums {
		// complement 是我们需要找的另一个数
		complement := target - num

		// 如果 complement 已经在 map 中，说明找到了答案
		// seen[complement] 是之前存的下标，i 是当前下标
		if idx, ok := seen[complement]; ok {
			return []int{idx, i}
		}

		// 把当前数值和下标存入 map，供后续元素查找
		seen[num] = i
	}

	// 题目保证有解，这里不会执行到
	return nil
}

执行过程演示

以 nums = [2, 7, 11, 15], target = 9 为例：

只遍历到第二个元素就找到了！

Go 写法要点

• make(map[int]int, len(nums)) — 预分配容量，减少扩容开销
• for i, num := range nums — Go 的 range 遍历同时拿到索引和值
• if idx, ok := seen[complement]; ok — Go 经典的 comma-ok 惯用法，安全地检查 map 中是否存在某个 key

复杂度分析

• 时间复杂度： O(n) — 只遍历一次数组，map 查找 O(1)
• 空间复杂度： O(n) — 最多存 n 个键值对

为什么哈希表解法更优？

把”找 complement 是否存在”的操作从 O(n) 降到了 O(1)，总体从 O(n²) 优化到 O(n)。

这是 “用空间换时间” 的经典案例 —— 多用了 O(n) 的空间，换来时间上平方级的提升。

扩展思考

• 如果数组已经排序，可以用 双指针 解法（左右向中间逼近）
• 如果要返回所有可能的解（不只一组），哈希表需要改用 map[int][]int 存储多个索引
• 如果数组中存在多个相同值，map 会覆盖之前的索引，但题目保证只有一组答案，所以不影响