3. 哈希表

哈希表的几个重点：
哈希函数：一个将键值映射到哈希表某个位置的映射函数
冲突：哈希函数映射到哈希表的同一个地方，解决可以用链表法或线性探测法。
溢出：

242. 有效的字母异位词 简单
383. 赎金信 简单
49. 字母异位词分组 中等
438. 找到字符串中所有字母异位词 中等
349. 两个数组的交集 简单
350. 两个数组的交集 II 简单
202. 快乐数 简单
1. 两数之和 简单
454. 四数相加 II 中等

  1. 有效的字母异位词 383赎金信

    哈希表法：使用哈希表存放字符出现的次数，即++，再遍历另一个字符串，—。判断哈希表是否==0

  2. 字母异位词分组

    1. 方法一：排序+哈希表法，字母异位词在排序过后一定是相等的，所以可以对字符串进行排序，再利用哈希表来管理。（记住，哈希表的键值不能使复杂的结构，unordered_map是不能作为键值的）
    2. 方法二：计数+哈希表法。未完成

  3. 找到字符串中所有字母异位词

    计数+滑动窗口法，因为给出了条件字符串都是小写字母，那就可以用一个vector来计数。重点：滑动窗口中的vector不用每滑动一次就重新生成一次。可以一直维护同一个vector，往右移一次，就++s[right],—s[left - 1]，注意这个思想，可以剩下不少时间和空间

  4. 两个数组的交集

    哈希表法：unordered_set aux(vec.begin(), vec.end());可以这么初始化（可以用其他容器的迭代器初始化另一种类的容器）。在set里找元素除了可以使用std::find也可以使用set.find(val) == set.end()

  5. 两个数组的交集 II

    哈希表法：注意题目要求，给出出现次数小的。那么当aux[i] = 0时就不再加入返回值。

  6. 快乐数

    1. 数学法：先手算处满足和不满足条件的1-10的数字，再用find判断退出循环条件
    2. 哈希表法：因为数字会陷入无限循环，那么就一定有重复的数字，那么就可以用unordered_set来进行判断是否跳出循环，跳出循环后，如果n=1则返回true

  7. 两数之和

    1. 暴力法
    2. 哈希表法：如果存在解，那么target - nums[i]一定也在unordered_map里面。所以遍历数组，进行判断，没有就插入该元素，继续遍历。

  8. 四数相加 II

    哈希表法：两个数相加的值作为键值，再用这个键值在另一个unordered_map中找是否存在满足条件的键值，如果有则加入ret