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⁹
• 只会存在一个有效答案

二、题目解析

核心问题拆解

思考方向

三、算法解答

算法一：暴力枚举法

1. 算法原理描述

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

实现方式：

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

2. 算法解答过程

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

返回 [0, 1]

3. 算法原理图像解析

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. 算法原理图像解析

哈希表状态变化：

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. 使用范围

算法三：排序 + 双指针法（特殊场景）

⚠️ 注意：此方法会丢失原始下标，需要额外处理。仅适用于返回值而非下标的变体题目。

1. 算法原理描述

核心思想：利用有序数组的性质，使用双指针从两端向中间逼近。

实现方式：

1. 将数组排序
2. 设置左指针 left = 0，右指针 right = n-1
3. 计算 sum = nums[left] + nums[right]
   • 若 sum == target：找到答案
   • 若 sum < target：左指针右移（增大和）
   • 若 sum > target：右指针左移（减小和）

2. 算法解答过程

以 nums = [2, 7, 11, 15], target = 9 为例（已排序）：

3. 算法原理图像解析

双指针移动规则：

4. 算法代码

// 方法：保留原始下标的双指针解法
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 创建副本并排序，保留原始下标
        vector<pair<int, int>> numWithIndex;
        for (int i = 0; i < nums.size(); i++) {
            numWithIndex.push_back({nums[i], i});
        }
        sort(numWithIndex.begin(), numWithIndex.end());
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int sum = numWithIndex[left].first + numWithIndex[right].first;
            if (sum == target) {
                return {numWithIndex[left].second, numWithIndex[right].second};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return {};
    }
};

5. 复杂度分析

6. 使用范围

四、三种算法对比

💡 面试建议

五、知识点总结

1. 涉及的数据结构

2. 涉及的算法思想

3. C++ 知识点

// 1. unordered_map 的使用
#include <unordered_map>
unordered_map<int, int> map;
map[key] = value;           // 插入
map.find(key);              // 查找，返回迭代器
map.count(key);             // 返回 0 或 1
map.end();                  // 结束迭代器
// 2. vector 的初始化返回
return {a, b};              // 直接返回初始化列表
// 3. pair 的使用
pair<int, int> p = {value, index};
p.first;                    // 第一个元素
p.second;                   // 第二个元素

六、做题模板

「两数之和」类问题通用模板

/*
 * 两数之和问题模板
 * 适用于：在数组中寻找满足 nums[i] + nums[j] = target 的配对
 */
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Step 1: 创建哈希表
        // key: 数组元素值
        // value: 元素下标
        unordered_map<int, int> hashMap;
        // Step 2: 遍历数组
        for (int i = 0; i < nums.size(); i++) {
            // Step 3: 计算配对值
            int complement = target - nums[i];
            // Step 4: 在哈希表中查找配对值
            if (hashMap.find(complement) != hashMap.end()) {
                // 找到配对，返回结果
                return {hashMap[complement], i};
            }
            // Step 5: 将当前元素加入哈希表
            hashMap[nums[i]] = i;
        }
        // Step 6: 未找到（题目保证有解时不会执行）
        return {};
    }
};

模板流程图：

模板变体

变体1：返回所有配对

vector<vector<int>> twoSumAll(vector<int>& nums, int target) {
    unordered_map<int, vector<int>> hashMap;  // 存储所有下标
    vector<vector<int>> result;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (hashMap.count(complement)) {
            for (int j : hashMap[complement]) {
                result.push_back({j, i});
            }
        }
        hashMap[nums[i]].push_back(i);
    }
    return result;
}

变体2：有序数组（双指针）

vector<int> twoSumSorted(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return {left, right};  // 注意：这里返回的是下标
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {};
}

七、相关题目推荐

八、面试高频问答

Q1: 为什么哈希表法要先查找再存入？

答：为了避免同一元素被使用两次。例如 nums = [3], target = 6，如果先存入再查找，会错误地返回 [0, 0]。

Q2: 如果有多个答案怎么办？

答：题目保证只有一个答案。若需返回所有答案，需要使用 unordered_map<int, vector<int>> 存储所有下标。

Q3: 哈希表 vs 红黑树（map vs unordered_map）？

答：

• unordered_map：哈希表，查找 O(1)，无序
• map：红黑树，查找 O(log n)，有序

本题不需要有序，选择 unordered_map 更优。

Q4: 时间复杂度 O(n) 是最优吗？

答：是的。至少需要遍历一次数组才能确定答案，O(n) 是下界。

九、一图总结