【LeetCode 题解】两数之和（C++/Python 双解法）：从语法到算法的全面解析-海口c网

【LeetCode题解】两数之和（C++/Python双解法）：从语法到算法的全面解析

一、题目描述

题目链接：1. 两数之和
难度：简单
要求：给定一个整数数组 nums 和一个整数目标值 target，在数组中找出两个数，使其和为 target，并返回它们的下标。
限制：每个输入只对应唯一解，且不能重复使用同一个元素。

二、解法思路：哈希表（最优解）

2.1 核心思想

暴力枚举：遍历每个元素，再嵌套遍历寻找补数（target - nums[i]），时间复杂度为 O(n²)，效率低。
哈希表优化：用哈希表（字典）存储元素及其下标，遍历数组时，对每个元素 nums[i]，检查补数是否已在哈希表中：
- 若存在，直接返回补数的下标和当前下标。
- 若不存在，将当前元素和下标存入哈希表，供后续元素查找。
时间复杂度：O(n)，只需遍历数组一次。
空间复杂度：O(n)，哈希表存储最多 n 个元素。

2.2 哈希表原理图解

哈希表查找补数示意图

三、代码实现

3.1 Python 解法

常规版（适合LeetCode直接提交）

from typing import Listclass Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:d = {}  # 键：元素值，值：下标for i in range(len(nums)):complement = target - nums[i]if complement in d:return [d[complement], i]d[nums[i]] = ireturn []  # 题目保证有解，此句可省略

ACM版（适合本地ACM模式输入）

# 读取输入
import sysdef main():data = list(map(int, sys.stdin.read().split()))n = data[0]target = data[1]nums = data[2: 2+n]d = {}for i in range(n):complement = target - nums[i]if complement in d:print(d[complement], i)returnd[nums[i]] = iif __name__ == "__main__":main()

ACM输入说明：

sys.stdin.read() 读取全部输入，适用于多行或连续输入场景。
输入格式示例：4 9 2 7 11 15（依次为n, target, 数组元素）。

3.2 C++ 解法

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> numToIndex; // 哈希表：存储元素值到下标的映射for (int i = 0; i < nums.size(); i++) {int complement = target - nums[i];// 查找补数是否在哈希表中if (numToIndex.find(complement) != numToIndex.end()) {return {numToIndex[complement], i}; // C++11列表初始化}numToIndex[nums[i]] = i; // 存入当前元素和下标}return {}; // 题目保证有解，此句可省略}
};// 主函数（ACM输入模式）
int main() {int n, target;cin >> n >> target; // 读取n和targetvector<int> nums(n); // 创建长度为n的数组for (int i = 0; i < n; i++) {cin >> nums[i]; // 读取数组元素}Solution solution;vector<int> result = solution.twoSum(nums, target);cout << result[0] << " " << result[1] << endl; // 输出结果return 0;
}

// #include <xxx> 引入工具包 
#include <iostream>         // 输入输出 cin >> 输入  cout << 输出
#include <unordered_map>    // 哈希工具包, 快速查询字典
#include <vector>           // 动态工具包, 存储一组数组using namespace std;         // 简化代码, 标准库工具。后面用到工具时, 不用写std:: 前缀// 类和函数！
class Solution {             // class是模板, Solution是模板名字// 比如“汽车”是个模板, 里面包含"启动", "刹车"等功能
public:     //模板里面的功能默认是“私有的”, public 让后面的函数可以被外部调用！vector<int> twoSum(vector<int>& nums, int target) {/*  vector<int> twoSum(...) 表示twoSum这个函数的返回值是一组整数(动态数组) vector<int>twoSum 函数名称vector<int>& nums 是函数输入的一组整数（vector<int>）& 表示“引用”, 直接使用原始数据, 不复制一份int target 另一个输入参数  */unordered_map<int, int> numToIndex; // 创建一个哈希表 <数字, 下标>for (int i = 0; i < (int)nums.size(); i++) {// for (起点 ; )int complement = target - nums[i]; // 计算需要的补数 // numToIndex.find(complement) 是在哈希表中查找是否有“单词”(“键值对中的键”)等于complement// 如果find到complement：返回这个单词对应的条目// 如果没找到,返回一个特殊标记 告诉我们 字典中没有这个单词！// end()方法： 是一个虚拟位置，字典的最后一个条目的后面 就是空！// 所以 如果find(xx) == end()  就是没找到这个单词if (numToIndex.find(complement) != numToIndex.end()) {// 如果补数complement就在哈希表中，如果找到了 且不等于end()return { numToIndex[complement], i };}// 如果没找到,把当前数和下标放入哈希表numToIndex[nums[i]] = i;}return {};}
};// main()函数是程序的入口
int main(){int n, target;cin >> n >> target; // cin >> ... >> ... 输入vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i]; // 读取n个整数存入数组}Solution solution; // 创建一个Solution类型的对象（类似造一辆车！名字叫做solution）vector<int> result = solution.twoSum(nums, target);cout << result[0] << " " << result[1] << endl;return 0;
}

四、C++语法关键点解析

4.1 分号 `;` 的使用规则（超详细总结）

4.1.1 必须加分号的情况

场景	示例代码	说明
语句末尾	`int a = 10;` `cout << "a";`	每个完整语句结束后必须加分号
单行控制流语句	`if (a>0) cout << "正数";`	单行if/while语句末尾加分号
类成员声明	`class A { int x; void f(); };`	成员变量和函数声明后加分号
枚举/联合体定义	`enum Color {RED, GREEN};`	定义末尾必须加分号

4.1.2 绝对不加分号的情况

场景	错误代码	正确代码	说明
函数体结束 `}`	`void f() { ... };`	`void f() { ... }`	函数体大括号后不加分号
预处理指令	`#include <iostream>;`	`#include <iostream>`	`#include`等指令后不加分号
类定义结束 `}`	`class A { ... }`	`class A { ... };`	唯一例外：类定义后必须加分号
大括号代码块内部	`if (a) { cout << "a"; ; }`	`if (a) { cout << "a"; }`	大括号内语句末尾加分号，括号后不加

4.1.3 易混淆场景对比

// 正确：类定义后加分号
class Solution { // 成员函数
}; // 错误：函数体后加分号
int main() { // 代码块
}; // ❌ 多余分号

4.2 哈希表关键操作：`find` vs `end`

unordered_map<int, int> numToIndex;
if (numToIndex.find(complement) != numToIndex.end()) {// 找到补数，返回下标
}

find(key)：在哈希表中查找键 key，若存在返回对应迭代器，否则返回 end()。
end()：返回一个指向哈希表“虚拟末尾”的迭代器，用于判断查找是否失败。
类比：相当于在字典中查找单词，找到返回单词位置，找不到返回“字典最后一页的下一页”（不存在）。

五、常见错误与解决方案

5.1 C++编译错误：`unordered_map` 未声明

原因：未启用C++11标准，或头文件缺失。
解决方案：
1. 添加 #include <unordered_map>。
2. 编译时加参数 -std=c++11：
```
g++ code.cpp -o output -std=c++11
```

5.2 类定义末尾缺少分号

class Solution { // 成员函数
} // ❌ 错误：缺少分号

修正：在类定义结束的 } 后添加分号：

class Solution { // 成员函数
}; // ✅ 正确

5.3 Python ACM输入错误：下标越界

原因：输入格式错误，如未正确解析n和数组长度。
解决方案：确保输入数据长度正确，如 nums = data[2: 2+n] 需与n匹配。

六、总结

6.1 算法优化对比

方法	时间复杂度	空间复杂度	适用场景
暴力枚举	O(n²)	O(1)	n很小的情况
哈希表	O(n)	O(n)	大规模数据

6.2 学习建议

C++语法：重点掌握分号规则、命名空间、STL容器（如vector、unordered_map）。
算法思维：学会用哈希表优化查找问题，理解空间换时间的思想。
代码习惯：
- 编译C++时默认启用C++11（-std=c++11）。
- 用IDE（如VS Code）实时检查语法错误。

示例输入输出：

输入：nums = [2,7,11,15], target = 9
输出：[0, 1]
解释：2 + 7 = 9，下标分别为0和1。

作者：CodeIsLife
博客链接：https://blog.csdn.net/CodeIsLife
转载请注明出处
欢迎在评论区交流疑问，觉得有帮助可以点赞收藏～ 😊

【LeetCode 题解】两数之和（C++/Python 双解法）：从语法到算法的全面解析