1.两数之和__C++
题目
给定一个整数数组 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 <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
方法一：暴力遍历
解题思路：内外循环，暴力遍历整个数组，一次遍历两个不同元素，判断，找到目标值，不超时
时间复杂度O(n^2) 空间复杂度O(1)
class Solution {public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i < nums.size(); i++){for(int j = i+1; j < nums.size(); j++){if(nums[i] + nums[j] == target){return {i,j};}}}return {0};}};
进阶： 你可以想出一个时间复杂度小于 O(n2) 的算法吗？
方法二：哈希表
解题思路： 使用哈希表unordered_map无序map实现 降低时间复杂度
时间复杂度O(N)) 空间复杂度O(N)
核心思想：
- 哈希表的作用：就像一个"备忘录"，记录已经遍历过的数字和它们的索引位置
- 补数的概念：对于当前数字
nums[i]，另一个需要的数字是target - nums[i] - 查找过程：一边遍历数组，一边在备忘录中查找是否存在需要的补数
class Solution {public:vector<int> twoSum(vector<int>& nums, int target) {//创建一个unorderd_map容器 每个pair对儿中key存放数组的下标 value存放对应下表数组的值 unordered_map<int,int> m;//unordered_map 对于已经学过map容器的朋友，可以将unordered_map容器等价为无序的map容器。// 遍历数组中的每个数字for(int i = 0; i < nums.size(); i++){// 计算当前数字的"补数"（即需要找到的另一个数）unordered_map<int,int>::iterator it = m.find(target-nums[i]);// 如果找到了补数（即 it 不等于 m.end())if(it != m.end()){// 返回补数的索引和当前元素的索引return {it->second,i};}// 如果没找到，把当前数字和它的索引存入哈希表//nums[i]作为key i作为value 存放到哈希表m[nums[i]] = i;}return {0};}};
简单分析：m[nums[i]] = i;
当执行 m[nums[i]] = i; 时，实际发生了以下操作：
| 组件 | 表达式 | 作用 | 示例（假设 nums = [2,7,11,15], i=1） |
|---|---|---|---|
| 键（key） | nums[i] |
获取当前数组元素作为键 | nums[1] = 7 → key = 7 |
| 值（value） | i |
获取当前索引作为值 | i = 1 → value = 1 |
| 赋值操作 | m[key] = value |
将键值对存入哈希表 | m[7] = 1 |
好处：
- 快速查找：通过键快速定位位置，时间复杂度接近 O(1)
- 空间换时间：使用额外空间存储索引，避免暴力双重循环
小白总结
- 用哈希表记录已访问的数字和位置
- 对每个数字，计算它需要的"搭档"（补数）
- 在哈希表中快速查找这个搭档
- 找到就返回结果，没找到就继续遍历
这个解法既高效又巧妙！