作为LeetCode题库的第一道题，两数之和几乎是所有开发者算法入门的必经之路。这道题看似简单，却完整覆盖了数组基础遍历、哈希表核心应用，以及「空间换时间」这一算法领域最经典的优化思想。无论是刚接触算法的新手，还是复盘基础的开发者，都能从这道题中吃透算法优化的核心逻辑。本文就从最直观的解法入手，一步步拆解这道经典题的解题思路与最优实现。

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

需要注意的是：

  1. 每种输入只会对应一个答案；
  2. 不能使用两次相同的元素；
  3. 可以按任意顺序返回答案；
  4. 数据范围：2 <= nums.length <= 10^4，-10^9 <= nums[i] <= 10^9，-10^9 <= target <= 10^9。

我们给出示例如下：

输入 目标值 输出 解释
[2,7,11,15] 9 [0,1] nums[0] + nums[1] = 2 + 7 = 9
[3,2,4] 6 [1,2] nums[1] + nums[2] = 2 + 4 = 6
[3,3] 6 [0,1] 两个3分别对应下标0和1，符合要求

题目的核心诉求非常明确，找到两个数的和等于目标值，返回它们的原始下标，而非数值本身。

方法一：暴力枚举

暴力枚举是最符合人类直觉的解法，既然要找两个数的和等于target，那我们就枚举数组中的每一个数 x，再去数组中寻找是否存在 target - x，找到后直接返回两个数的下标即可。这里有一个关键的细节优化，每一个位于 x 之前的元素，都已经和 x 完成过匹配检查，因此无需重复校验。同时为了避免使用同一个元素两次，我们只需要在x后面的元素中寻找 target - x 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // n = 数组的长度
        int n = nums.size();
        // 外层循环：第一个数 i，从 0 开始遍历到最后
        for (int i = 0; i < n; ++i) {
            // 内层循环：第二个数 j，从 i+1 开始（避免自己和自己配对）
            for (int j = i + 1; j < n; ++j) {
                // 判断：第i个数 + 第j个数 是否等于 target
                if (nums[i] + nums[j] == target) {
                    // 找到直接返回下标 i 和 j
                    return {i, j};
                }
            }
        }
        // 题目保证一定有答案，这里只是防止语法报错
        return {};
    }
};

外层循环逐个取出数组中的第一个数字，内层循环从这个数字的下一位开始，遍历后续所有数字与之配对。这样做既能避免重复检查，也能保证不使用同一个元素两次，当找到一组数字相加等于目标值时，直接返回这两个数字对应的下标。

复杂度分析

  • 时间复杂度：O(N^2^)，其中N是数组的元素数量。最坏情况下，数组中任意两个数都需要被匹配一次，两层嵌套循环的时间复杂度为平方级。
  • 空间复杂度：O(1)。仅使用了常数个临时变量，没有开辟与数据规模相关的额外空间，属于原地算法。

return {i, j}; 是 C++ 语言的简化写法，作用是直接返回一个包含两个整数 i、j 的 vector<int> 容器（数组）,这将返回答案数组，里面放着两个数的下标 [i, j]。

尽管这种解法逻辑极简、直观易懂，无需额外的数据结构知识，代码编写零门槛，在数据量极小时可以快速实现。但时间复杂度过高，当数组长度达到题目上限10^4^时，最坏情况需要执行10^8^次操作，在算法判题中极易超时，无法应对大规模数据场景。

方法二：哈希表

暴力法的性能瓶颈非常明确，每次寻找 target - x 的操作，都需要遍历一次数组，查找的时间复杂度为O(N^2^)。算法优化的核心，就是针对这个耗时环节，找到更高效的实现方式。而哈希表正是解决这个问题的最优选择。哈希表的核心特性，就是支持平均O(1)时间复杂度的元素查找与插入。我们可以用哈希表存储已经遍历过的元素值和它对应的数组下标，这样遍历到当前元素x时，只需要一次O(1)的查询，就能知道之前是否出现过 target - x。

这里有一个关键的执行顺序：先查询哈希表，再将当前元素插入哈希表。这个顺序可以保证不会出现当前元素和自己匹配的情况（比如target=6、当前元素=3时，不会自己和自己配对），完全符合题目不能使用两次相同元素的要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 哈希表：key为数组元素值，value为元素对应的下标
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            // 先查询哈希表中是否存在target - 当前元素
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                // 找到目标值，返回之前元素的下标和当前下标
                return {it->second, i};
            }
            // 未找到，将当前元素和下标存入哈希表，供后续元素查询
            hashtable[nums[i]] = i;
        }
        // 题目保证有解，此处仅为语法合规
        return {};
    }
};

代码首先创建一个哈希表，用来存储已经遍历过的数组元素，以及元素对应的下标。随后开始遍历数组中的每一个元素，先在哈希表中查找是否存在目标值 - 当前元素，如果存在，就说明已经找到了满足条件的两个数，直接返回哈希表中存储的下标和当前元素的下标。

如果没有找到匹配的数值，就将当前元素和它的下标存入哈希表，供后续元素匹配使用。因为遵循先查询、后存储的规则，所以不会出现同一个元素被重复使用的情况。代码最后返回空数组，只是为了满足语法要求，题目保证存在有效解，这行代码永远不会被执行。

复杂度分析

  • 时间复杂度：O(N)，其中N是数组的元素数量。我们仅需要遍历数组一次，每个元素的哈希表查询和插入操作均为O(1)，整体为线性时间复杂度。
  • 空间复杂度：O(N)，其中N是数组的元素数量。最坏情况下，需要将数组中所有元素都存入哈希表，主要开销为哈希表的存储空间。这是典型的空间换时间优化思路，用可接受的额外空间，换取了时间复杂度的量级提升。

此解法的时间复杂度达到了线性级别，哪怕数组长度达到题目上限10^4^，也能轻松完成计算，是这道题的工业级最优解。但需要额外的哈希表存储空间，但在绝大多数业务和算法判题场景中，这个空间开销完全可以忽略不计。

除此之外，很多人还会想到排序加双指针的解法，这里做一个简单的说明：排序加双指针的核心逻辑，是先对数组进行排序，再用左指针指向数组开头、右指针指向数组结尾，根据两数之和与target的大小关系移动指针，最终找到目标值。这个方法的时间复杂度为O(NlogN)（主要来自排序的开销），优于暴力枚举，但远不如哈希表解法。更关键的是，这道题要求返回元素的原始下标，而排序会直接打乱数组的原始顺序，我们需要额外的空间存储每个元素排序前的下标，实现复杂度大幅上升，性价比远低于哈希表解法。因此在这道题中，哈希表是无可争议的最优选择。