两数之和 暴力解法

在 LeetCode 的入门题目中，“两数之和”（Two Sum）绝对是绕不开的经典。这道题看似简单，却能帮我们夯实数组遍历、条件判断等基础编程能力。今天就来聊聊这道题的暴力解法思路，以及完整的 C++ 实现。

题目回顾

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

注意：

• 每种输入只会对应一个答案。
• 你可以假设每种输入只会对应一个答案，且同一个元素不能使用两遍。
• 你可以按任意顺序返回答案。

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

暴力解法思路

暴力解法的核心逻辑非常直观：遍历所有可能的数对，检查它们的和是否等于目标值。

具体步骤：

1. 外层循环遍历数组中的每一个元素，下标记为i（从 0 开始，遍历到倒数第二个元素即可，因为内层会找后续元素）；
2. 内层循环遍历i之后的所有元素，下标记为j（从i+1开始，避免重复检查同一对数，也避免使用同一个元素两次）；
3. 对于每一对(nums[i], nums[j])，判断它们的和是否等于target；
4. 一旦找到符合条件的数对，立即返回它们的下标[i, j]；
5. 题目保证有且仅有一个答案，因此循环结束前必定能找到结果。

C++ 代码实现

cpp

运行

#include <vector> using namespace std; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int i, j; // 外层循环：遍历到倒数第二个元素即可 for (i = 0; i < nums.size() - 1; i++) { // 内层循环：从i的下一个元素开始，避免重复 for (j = i + 1; j < nums.size(); j++) { // 找到和为target的数对，直接返回下标 if (nums[i] + nums[j] == target) { return {i, j}; } } } // 题目保证有解，此处仅为语法兼容 return {i, j}; } };

代码解析

1. 变量定义：声明两个整型变量i和j，分别作为外层和内层循环的下标；
2. 外层循环：i从 0 遍历到nums.size() - 2（因为nums.size() - 1是最后一个元素的下标，i到倒数第二个即可，j会取最后一个）；
3. 内层循环：j从i+1开始遍历到数组末尾，确保每个数对只检查一次；
4. 条件判断：若nums[i] + nums[j] == target，直接返回包含下标i和j的 vector；
5. 兜底返回：题目明确有且仅有一个解，因此这行代码不会被执行，仅为满足函数的返回语法要求。

复杂度分析

• 时间复杂度：O (n²)。外层循环执行 n 次，内层循环平均执行 n/2 次，总的时间复杂度为平方级。
• 空间复杂度：O (1)。仅使用了常数个临时变量，没有额外开辟与输入规模相关的空间。

总结

暴力解法是两数之和最基础的解法，优点是思路简单、代码易实现，适合算法入门者理解 “遍历 + 匹配” 的核心思想；缺点是时间效率较低，当数组规模较大（如 n>10⁴）时，运行时间会显著增加。

后续还可以优化为哈希表解法（时间复杂度 O (n)），感兴趣的同学可以继续深入研究。刷题的核心不是记住答案，而是理解每一种解法的思路和适用场景，逐步培养算法思维。