一，哈希表简介
哈希思想是算法中一个十分重要的思想，体现的是一种映射关系，而哈希表就是基于哈希思想实现的存储数据的容器。哈希表的作用是快速查找某个元素，时间复杂度为 O(1)，遍历数组的时间复杂度为 O(N)。
使用哈希一般有两种方式： (1) STL 中的 unordered 系列容器。 (2) 用数组模拟简易哈希表。这种情况一般用于处理字符串中的'字符'或是当数据范围很小的时候使用。
下面将通过若干道题目进一步体会哈希表的使用。
二，算法原理和代码实现
1. 两数之和
算法原理：
(1) 如果我们可以事先将数组内的元素和下标绑定在一起存入哈希表中，然后直接在哈希表中查找每一个元素的 target - nums[i]，就能快速的找到目标和的下标。 (2) 这里有一个小技巧，我们不用将元素全部放入到哈希表之后，再来二次遍历 (因为要处理元素相同的情况)。而是在将元素放入到哈希表中的同时，直接来检查表中是否已经存在当前元素所对应的目标元素 (即 target - nums[i])。如果它存在，那我们已经找到了对应解，并立即将其返回。无需将元素全部放入哈希表中，提高效率。 (3) 因为哈希表中查找元素的时间复杂度是 O(1)，遍历一遍数组的时间复杂度为 O(N)，因此可以将时间复杂度降到 O(N)。
代码实现：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash; // 存元素和对应的下标
for (int i = 0; i < nums.size(); i++) {
// 检查在该元素之前是否存在一个数等于 target-nums[i]
int x = target - nums[i];
if (hash.count(x)) return {hash[x], i};
hash[nums[i]] = i; // 不存在就插入
}
return {-1, -1};
}
};
349. 两个数组的交集
算法原理：
解法 1：使用哈希表。
