力扣100题——1.两数之和

1.题目：两数之和

给定一个整数数组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(n2)的算法吗？

使用哈希函数解决问题

用哈希表来解决复杂度为o(n), c++语言自带哈希函数。

2.代码：

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { // vector动态数组，nums定义为动态数组可以使用size函数 unordered_map<int,int> seen; //key:数字， value：下标值 seen初始为空 for(int i=0;i<nums.size();i++){ int need=target-nums[i]; auto it =seen.find(need); if(it!=seen.end()){ //seen.end()查找失败标记 return {it->second,i}; } seen[nums[i]]=i; //查找失败则将该数据存入seen中 } return {}; } };

3.具体解析：

auto it = seen.find(need);`

①seen.find(need)

seen是unordered_map<int,int>（哈希表）。.find(键)：在哈希表里查找 key = need 这个数。

返回值：

• 如果找到了 → 返回一个迭代器 (iterator)，指向这个键‑值对

• 如果找不到 → 返回seen.end()，代表「末尾空位置，没找到」

② 什么是迭代器it

你可以把迭代器it理解成指向 map 里面某一条记录的指针。 一条 map 记录是一对：pair<int, int>

• it->first→ key（存的数字）

• it->second→ value（数字对应的下标）

③ 为什么用auto？

find返回的类型很长，完整写出来是：

unordered_map<int,int>::iterator it = seen.find(need);

auto让编译器自动推导左边变量的类型，不用你手写一长串迭代器类型。 效果完全等价，只是简写。

机试写代码强烈推荐 auto，省时，不容易写错类型。

---

return {it->second, i};的本质

这个{ ... }叫做列表初始化（uniform‑initialization）作用：临时构造一个 vector<int> 对象，把两个整数放进去。

它等价于：

vector<int> temp;

temp.push_back(it->second);

temp.push_back(i);

return temp;

① 值传递（不带 &）：vector<int> nums

vector<int> twoSum(vector<int> nums, int target)

程序会把外面整个 vector 完完整整复制一份，在函数内部生成一个全新、独立的数组。

• 两块不同内存

• 修改函数里 nums 不会影响外面原数组

• 缺点：数组很大时复制非常慢，浪费内存

② 引用传递（带 &）：vector<int>& nums

vector<int> twoSum(vector<int>& nums, int target)

不拷贝！函数内 nums 只是原数组的外号。

• 只有一块内存

• nums 和原数组就是同一个东西

• 修改 nums 会直接改到外面原始数组

  ---