LeetCode 1：两数之和（Two Sum）

给定一个整数数组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⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 只会存在一个有效答案

二、题目解析

核心问题拆解

思考方向

原问题

nums[i] + nums[j] = target

转化思维

对于每个 nums[i]
寻找 target - nums[i]

如何快速查找?

哈希表 O(1)

三、算法解答

算法一：暴力枚举法

1. 算法原理描述

核心思想：穷举所有可能的两数组合，检查它们的和是否等于目标值。

实现方式：

• 使用两层循环
• 外层循环固定第一个数nums[i]
• 内层循环遍历其后的所有数nums[j]（j > i）
• 检查nums[i] + nums[j] == target

2. 算法解答过程

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

返回[0, 1]

3. 算法原理图像解析

复杂度分析

⏱ 时间: O(n²)

💾 空间: O(1)

暴力枚举流程

✅ 是

❌ 否

开始

外层循环 i = 0

内层循环 j = 1

nums[0] + nums[1]
= 2 + 7 = 9
== target?

返回 [0, 1]

j++, 继续内层

若内层结束
i++, 继续外层

数组 nums, target = 9

[0]=2

[1]=7

[2]=11

[3]=15

4. 算法代码

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); // 外层循环：固定第一个数 for (int i = 0; i < n - 1; i++) { // 内层循环：遍历第一个数之后的所有数 for (int j = i + 1; j < n; j++) { // 检查两数之和是否等于目标值 if (nums[i] + nums[j] == target) { return {i, j}; } } } // 题目保证有解，这里不会执行到 return {}; } };

5. 复杂度分析

6. 使用范围

算法二：哈希表法（一遍哈希）⭐ 最优解

1. 算法原理描述

核心思想：将「寻找两数之和」转化为「寻找差值」问题。

关键转换：

nums[i] + nums[j] = target ↓ 转化 nums[j] = target - nums[i]

实现方式：

• 使用哈希表存储已遍历过的元素及其下标
• 对于当前元素nums[i]，计算complement = target - nums[i]
• 在哈希表中查找complement是否存在
• 若存在，说明找到答案；若不存在，将当前元素加入哈希表

优势：哈希表的查找时间复杂度为 O(1)，整体只需一次遍历。

2. 算法解答过程

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

3. 算法原理图像解析

🔑 核心要点

边遍历边建表

先查找再存入

O(1) 查找

步骤2: 处理 nums[1] = 7

计算 complement = 9 - 7 = 2

哈希表中
查找 2

✅ 找到! 下标=0

返回 [0, 1]

步骤1: 处理 nums[0] = 2

计算 complement = 9 - 2 = 7

哈希表中
查找 7

❌ 未找到

存入哈希表
{2: 0}

输入: nums = [2,7,11,15], target = 9

2

7

11

15

哈希表状态变化：

存入 2:0

查找2

处理7时

2 → 0

查找2 ✅

处理2后

2 → 0

初始状态

空 ∅

4. 算法代码

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { // 哈希表：key = 数值，value = 下标 unordered_map<int, int> hashMap; for (int i = 0; i < nums.size(); i++) { // 计算当前元素的"配对值" int complement = target - nums[i]; // 在哈希表中查找配对值 if (hashMap.find(complement) != hashMap.end()) { // 找到了！返回两个下标 return {hashMap[complement], i}; } // 未找到，将当前元素存入哈希表 hashMap[nums[i]] = i; } // 题目保证有解，这里不会执行到 return {}; } };

5. 代码详解

// 关键点解析： // 1. 为什么用 unordered_map 而不是 map？ // - unordered_map 基于哈希表，查找/插入 O(1) // - map 基于红黑树，查找/插入 O(log n) // 2. 为什么先查找再存入？ // - 避免同一元素被使用两次 // - 例如：nums = [3, 3], target = 6 // - 第一个3存入后，第二个3能找到第一个3 // 3. hashMap.find() vs hashMap.count() // - find() 返回迭代器，未找到返回 end() // - count() 返回 0 或 1 // - 两种写法都可以，find() 更常用

6. 复杂度分析

7. 使用范围