[leetcode数组系列]1两数之和
# 前言
>秋招的结束，面试了大大小小的公司，最大的问题在于算法上。所以打算坚持在leetcode打卡，看看到底能不能行，如果你想见证，那我来开车，你坐稳，一起走向更好的远方。2020=1024+996，准备好了？
# 一 题目
>给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
>
>你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
1 leetcode链接
>https://leetcode-cn.com/problems/two-sum/
示例
>给定 nums = [2, 7, 11, 15], target = 9
>
>因为 nums[0] + nums[1] = 2 + 7 = 9
>所以返回 [0, 1]
2 思路1---暴力解法
我们需要在一个数组nums中寻找两个数，然后呢这个两个数之和需要等于目标的值。ok，我的外层循环从第一个数开始遍历，内层循环从第二个数遍历，如果这两个数和等于目标值，我就返回下标，**问题来了**，我要返回下标，所以需要先暂存起来才方便，而且返回的类型也需要确定。在这里，我的返回类型为vector
```c++
class Solution {
public:
vector
//int result[]={0.1};
int i=0;
int j=0;
for(i;
i
for(j=i+1;
j
if(nums[i]+nums[j]==target)
{
return {i,j};
}
}
}
return {i,j};
}
};
```
3 思路2---上hash
首先咋们想想hash是个什么玩意儿，存在既有意义嘛。从定义来说是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。那我们看看下图，看NBA的童鞋应该知道下面的几位大佬，他们也有对应的外号，这样就形成了key value的hash结构。
ok，那有些小伙伴有想法了，貌似很多明星都有好几个外号呀，比如哈登还有大胡子的外号怎么办，这里咱们可以使用拉链法的方式如下图。
好了，我们大概知道hash的一点点基本原理，然后这个题目怎么使用hash来解决呢？
- 确定返回值类型为vector
- 在c++中类似hash这种key，value的容器有map,unorder_map等，我们选择unordered_map。
- 循环遍历数组，每得到一个元素A，就去hash表中寻找是否存在target-A,注意，hash查找的时间复杂度为O(1)
```c++
class Solution {
public:
vector
vector
unordered_map
for(int i=0;
i < nums.size();
++i){
int another = target - nums[i];
if(hash_map.count(another)){
res = vector
return res;
}
hash_map[nums[i]] = i;
}
return res;
}
};
```
4 总结
> 文中使用了两种方式来解决这个问题，第一种为复杂度较高的暴力解答，第二种使用hash的方式来解答，其中了解hash的基本原理，后续会对hash进行详细的阐述以及应用场景。至此，咱们想想如何解决三数之和的问题呢？
5 结尾
>希望读者和咱一起一步一个脚印去把基础知识打牢固。如果读者发现有什么错误或者不太好的地方，欢迎私我，我会及时修改。
【[leetcode数组系列]1两数之和】
推荐阅读
- 【欢喜是你·三宅系列①】⑶
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 数组常用方法一
- 你不可不知的真相系列之科学
- 人脸识别|【人脸识别系列】| 实现自动化妆
- Java|Java基础——数组
- 2018-06-13金句系列7（金句结构-改编古现代诗词）
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- Unity和Android通信系列文章2——扩展UnityPlayerActivity