【题目】
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
【示例】
输入：nums = [3,2,4], target = 6
输出：[1,2]
【菜鸡思路】
如果直接暴力，时间复杂度就是n^2。一开始想的是先排序，排完序就可以分成（默认target是正的）比target大的，比target小的正数，负数三个部分。target=两个小的正数相加 或者 大的和负数相加。如果是两个小的正数，就还是遍历，但这个时候是有序的，当和大于target时可以跳出此时的循环。大的和负的也一样的思路。hh最后发现完全不对，不能排序，排完序下标变了。而且就算是这样也还是n^2。
【累了，以我的知识面，不如直接看看答案】
n^2的病灶：寻找 target - x（原来这小地方还拐了个弯） 的时间复杂度过高。
改进：使用哈希表，可以将寻找 target - x 的时间复杂度降低到从O(N) 降低到O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};很好，其实我没看太明白。
【先来复习一下哈希表这个无比久远的知识点】
1.哈希函数：从key到value的映射。 value=H(key)。
2.哈希冲突：映射不唯一，不同的key可能对应同一个value。
3.哈希表（unordered_map）:
头文件：本名 #include <unordered_map>
定义形式：
模板定义
template < class Key, //键值对中键的类型
class T, //键值对中值的类型
class Hash = hash<Key>, //容器内部存储键值对所用的哈希函数
class Pred = equal_to<Key>, //判断各个键值对键相同的规则
class Alloc = allocator< pair<const Key,T> > // 指定分配器对象的类型
> class unordered_map;一般来说，只需要 unordered_map<key的类型，value的类型> 表名
unordered_map<int,int> map={
pair<int,int>(1,3)
};
建立：假如关键字1对应值3
- map[1]=3
- map.insert<make_pair(1,3)>
- map.insert({1,3})
迭代器遍历
for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){
cout<<it->first<<it->second<<endl;
}
auto相当于it的前缀定义
常用成员函数
| at(key) | 返回容器中存储的键 key 对应的值，如果 key 不存在，则会抛出 out_of_range 异常。 |
| find(key) | 查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。 |
| count(key) | 在容器中查找以 key 键的键值对的个数。 |
| erase() | 删除指定键值对。 |
| clear() | 清空容器，即删除容器中存储的所有键值对。 |
| swap() | 交换 2 个 unordered_map 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等。 |
| equal_range(key) | 返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。 |
| emplace() | 向容器中添加新键值对，效率比 insert() 方法高。 |
| emplace_hint() | 向容器中添加新键值对，效率比 insert() 方法高。 |
【简单复习一下再次考虑】
确实哈，改用哈希表之后就只需要遍历1趟这n个数。把target-num[i]当作关键字key，最开始find(key)时，map里啥也没有，就把它自己nums[i]和下标i一起插到map里，不需要再遍历一趟。
【最后再简单复习一下map,hash_map,unordered_map区别】
map：
（适用场景：数据量小于1000或者对内存使用要求比较高）
底层是红黑树，空间复杂度O(n)，是随着节点的增加才增加，而查找的时间时间复杂度固定是O(log(n))。
特点：红黑树是一种二叉搜索树，所以从begin()遍历到end()得到的key值是有序的。
hash_map和unordered_map：
（适用场景：数据量大的话并且需要频繁查找）
hash表实现，使用开链法解决冲突问题。非有序。查找时间复杂度O(1)。
unordered_map的链表节点用的是称为bucket（桶）的数据结构。支持string做key，也可以使用复杂的对象作为key。而且现在基本都不用hash_map了。
【感想】
有没有真人带带我啊！麻了。。。
