🎈 作者：Linux猿
🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀
🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
🔶🔶🔶🔶🔶 点击观看视频版 🔶🔶🔶🔶🔶
面试被问“A+B”，我懵了
「算法」在面试中经常遇到，尤其「大厂」面试，另外今年「寒气逼人」，不管是「大厂」还是「小厂」都发了不少的「毕业证」，美其名曰：向社会输送人才。
算法难度也是刷新了高度，动不动就 Hard Hard Hard，说不定面试官为了出这一题也看了好久，也是煞费苦心！
这不相互为难吗？打工人何苦为难打工人呢！
但是，「鲁迅」说过：一口吃不了一个胖子，算法需要时长刷、走着刷、吃着刷，有时，白天不会，梦里说不定就解出来了。
那所有面试都问 Hard 难度的算法吗？当然不可能。
但是面试会问 A + B 吗？就是为了让你写出这代码？👇
class Solution {
public:
int Add(int num1, int num2) {
return num1 + num2;
}
};
那这面试有多水，直接进去不就行了！
本篇文章并不是说的表面上的 A + B，这里的 A + B 是代表一类问题，比如：A 和 B 是两个链表，比如：在一个数组中，寻找两个数的和等于 Target 等更深一层次的问题！
那下面来看一下 A 和 B 是两个链表的情况。
一、A + B 之两数之和
1.1 题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。
2 <= nums.length <= 10^4；
-10^9 <= nums[i] <= 10^9；
-10^9 <= target <= 10^9；
1.2 解题思路
1.2.1 方法一
拿到题目，最简单的方法是两层 for 循环，时间复杂度为 O(n^2)，代码如下所示：
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};「鲁迅」说过：刷题要精益求精，举一反三。
还有什么更好的方法呢！时间复杂度更低呢！
1.2.2 方法二
在第一种方法中，使用了两层 for 循环，可不可以把第一层 for 循环优化掉！明显不行，那第二层 for 循环呢！可以！
我们可以将遍历过的数存储到一个哈希表中，注意：哈希表存储和查询的可以看做是 O(1)，所有，第二层 for 循环改成哈希表处理后，时间复杂度变为 O(1)，总的时间复杂度为 O(n)。
代码如下所示：
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashTable; //哈希表
for (int i = 0; i < (int)nums.size(); ++i) { //依次遍历每一个元素
if (hashTable.count(target - nums[i])) {//查找 target - nums[i] 是否存在
return {i, hashTable[target - nums[i]]};
}
hashTable[nums[i]] = i;
}
return {};
}
};在上述代码中，通过将已经遍历过的数存储到 hashTable 中，然后，后面的元素遍历的时候在hashTable 中查找 target – nums[i] 即可。
时间复杂度为 O(n)。
好了，更多的 A + B 问题我们留到下一篇文章中讲解，敬请期待！
🎈 感觉有帮助记得「一键三连」支持下哦！有问题可在评论区留言💬，感谢大家的一路支持！🤞猿哥将持续输出「优质文章」回馈大家！🤞🌹🌹🌹🌹🌹🌹🤞
文章出处登录后可见！
