147 lines
4.2 KiB
Markdown
147 lines
4.2 KiB
Markdown
---
|
||
tags: ["LeetCode", "哈希表", "简单"]
|
||
create time: 2026-05-13 14:30
|
||
---
|
||
|
||
# 01-两数之和
|
||
|
||
## 题面
|
||
|
||
给定一个整数数组 `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]
|
||
```
|
||
|
||
**示例 3：**
|
||
|
||
```
|
||
输入：nums = [3,3], target = 6
|
||
输出：[0,1]
|
||
```
|
||
|
||
**约束：**
|
||
|
||
- `2 <= nums.length <= 10^4`
|
||
- `-10^9 <= nums[i] <= 10^9`
|
||
- `-10^9 <= target <= 10^9`
|
||
- 只会存在一个有效答案
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 思考
|
||
> 给定一个数字 x，如何快速判断 `target - x` 是否已经出现过？这就是本题的核心问题——"补数查找"。
|
||
|
||
### 方法一：暴力枚举（O(n²)）
|
||
|
||
最直接的想法：两层循环枚举所有数对，检查和是否等于 target。
|
||
|
||
这个方案虽然正确，但不符合进阶要求。我们直接进入最优解法。
|
||
|
||
### 方法二：哈希表一次扫描 ⭐（O(n)）
|
||
|
||
核心思想：**用空间换时间**。在遍历数组的同时，把已经走过的数字记录下来。每遇到一个新数字，先看看它的补数是否已经在记录里——找到了就返回，没找到就把当前数字放入记录，继续往后走。
|
||
|
||
为什么可以一遍完成？因为我们不需要「自己加自己」——题目明确说不让使用同一个元素两次，而我们是先查后放，当前元素还没入库时查到的肯定是之前其他位置的值。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["开始"] --> B{"遍历完数组?"}
|
||
B -->|"是"| C["无解, 返回空"]
|
||
B -->|"否"| D["取出当前值 num"]
|
||
D --> E["计算 complement = target - num"]
|
||
E --> F{"complement 在哈希表中?"}
|
||
F -->|"是"| G["返回 [[hash[complement]], 当前位置]"]
|
||
F -->|"否"| H["将 num → 索引 存入哈希表"]
|
||
H --> B
|
||
```
|
||
|
||
以 `nums = [2, 7, 11, 15], target = 9` 为例：
|
||
|
||
| 步骤 | 当前值 | 补数 | 哈希表状态 | 结果 |
|
||
|------|--------|------|------------|------|
|
||
| 1 | 2 | 7 | `{}` | 未找到，存入 `2→0` |
|
||
| 2 | 7 | 2 | `{2:0}` | **找到！** 返回 `[0, 1]` |
|
||
|
||
**关键细节：**
|
||
|
||
- Go 中使用 `map[int]int` 实现哈希表，键为数值、值为索引
|
||
- `val, ok := mp[key]` 的 ok 语义天然适合「判断 key 是否存在」
|
||
- 插入操作直接 `mp[num] = i`，简洁高效
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
```
|
||
// 伪代码模板
|
||
初始化空哈希表 mp
|
||
for i 从 0 到 n-1:
|
||
complement = target - nums[i]
|
||
if complement 在 mp 中:
|
||
return [mp[complement], i]
|
||
mp[nums[i]] = i
|
||
```
|
||
|
||
Go 语言中使用多返回值判断 key 是否存在：
|
||
|
||
```go
|
||
idx, exists := mp[complement]
|
||
if exists {
|
||
// found it!
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：补数查找
|
||
> 「两数之和」是补数查找的经典范式。任何「寻找两个元素满足某种和/差关系」的问题，都可以尝试这个模式：一边遍历一边维护已访问元素的哈希表。
|
||
|
||
> [!note] 🐹 Go 中的 HashMap 陷阱
|
||
> - Go 的 `map` 查找不存在的 key 会返回零值，所以必须用双返回值 `(val, ok)` 来区分「key 不存在」和「key 对应零值」
|
||
> - 本题不会出现此冲突（nums[i] ≥ 0 时），但处理负数或需要判断 nil 时要格外注意
|
||
|
||
> [!info] 📊 复杂度分析
|
||
> - 时间：O(n)，只扫描一次数组，每次哈希表操作均摊 O(1)
|
||
> - 空间：O(n)，最坏情况下需要存储 n-1 个元素
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
func twoSum(nums []int, target int) []int {
|
||
mp := make(map[int]int) // 数值 -> 索引的映射
|
||
|
||
for i, num := range nums {
|
||
complement := target - num
|
||
if idx, ok := mp[complement]; ok {
|
||
return []int{idx, i}
|
||
}
|
||
mp[num] = i
|
||
}
|
||
|
||
return nil // 理论上不会执行到此处（题目保证有解）
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 1 题，通过率约 50%，属于入门必会的经典题目。掌握补数查找模式后，类似变体如「两数之和 II」「四数之和」都能迎刃而解。
|