哈希表就是在关键字和存储位置之间建立对应关系。也就是：

  在C++中可以使用无序容器来实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 头文件
#include<unordered_map>
// 定义，这里表示key和value都是int型
unordered_map<int, int> map = {{1, 1}, {2, 2}, {3, 4}};
// 也可以指定key的类型
unordered_map<char, int> map;
// 如果没有指定元素，则map初始化的value为0
unordered_map<int, int> map;
// 迭代器
map.begin();
map.end();
// 添加 key 并统计重复的key个数
map[key]++;
// 添加 key 并去重
map[key];
// 添加指定的key和value
map[key] = value;
// 查找key（迭代器方式查找）
map.find(target);
// 返回指定key下的value
int value = map[key];

  可以看到map[key]既可以左赋值也可以右赋值，很灵活。

力扣 1

  两数之和
  在这里，对于一个固定值target，我要找到数组中的对应元素以及他们的下标，那就先建立起数组元素key和他们下标value的映射，这样就构建出了一个哈希表map，map用来存放遍历过的元素，比如示例1，当开始遍历元素2时，我想找到7是否遍历过，因为9-2=7，但是发现没有，因此更新哈希表，将key=2和value=0放进map表中，然后开始遍历7，在map中找有没有元素2，如果找到了，返回map中{2， 0}集合，取value=0和value=1，即构成了示例1的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> twoSum(vector<int>& nums, int target)
{
    unordered_map<int, int> idx;//构建<key, value>容器集合
    for(int i = 0; i < num.size(); i++)
    {
        auto it = idx.find(target - nums[i]);//查找有没有target - nums[i]
        if(it != idx.end())//如果找到了
        {
            return {it->second, i};//it->second是在取value
        }
        idx[nums[i]] = i;//更新哈希表
    }
    return {};
}

  使用哈希表的时间复杂度为$\small{O(N)}$，空间复杂度为$\small{O(N)}$。比暴力解法$\small{O(N^2)}$要快。

力扣 242

  有效的字母异位词
  这个题使用数组作为哈希表。由于s和t仅包含小写字母，可以统计两个字符串中26个小写字母出现的次数。如果s和t中26个字母出现的次数相等，说明t是s的字母异位词，如果不相等则不是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isAnagram(string s, string t)
{
    // 判断长度是否相等，不相等一定不是字母异位词。
    if(s.length() != t.length())
        return false;
    // 定义一个全零的一维数组，大小为26。
    int table[26] = {0};
    // 统计s中26个字母出现的次数
    for(auto& it: s)
        table[it - 'a']++;
    for(auto& it: t)
    // 统计t中26个字母出现的次数（做差）
        table[it - 'a']--;
    // 此时table中保存的是t和s的次数差值，如果table中元素全为0，说明t和s是字母异位词，每个字母使用次数相等。如果出现任何非零值，则不是。
    for(int i = 0; i < 26; i++)
        if(table[i] != 0) return false;
    return true;
}

力扣 349

  两个数组的交集
  这个题不适用数组作为哈希表进行解决，因为可能输入的数据量非常大，数组会增加存储开销。因此用 set 数据类型进行解决，set 和 map 一样，也是一类哈希表，不过只有一列数据。C++中可由下面定义：

1
2
3
4
5
6
7
8
9
10
//定义
unordered_set<int> set(vector<int>.begin(), vector<int>.end());
unordered_set<int> set();
//迭代器
set.begin();
set.end();
//插入数据并自动去重
set.insert(target);
//寻找目标数据（迭代器）
set.find(target);

  这里先将 nums1 转换为 set 数据，然后查找 nums2 中的元素在 set 表中是否存在，如果存在就将结果保存下来，最后输出。这里用 set 还有一个好处就是会自动去重，所以无需处理结果中可能存在的重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
    unordered_set<int> res;
    // 使用迭代器初始化set表
    unordered_set<int> table(nums1.begin(), nums1.end());
    // 遍历 nums2 中的元素
    for(int num : nums2)
    {
        // 迭代寻找 num 是否存在于表中
        if(table.find(num) != table.end())
            // 存在则保存结果（这里会实现去重）
            res.insert(num);
    }
    // 使用迭代器的方式将 set 类型转换为 vector<int> 类型
    return vector<int>(res.begin(), res.end());
}

  时间复杂度是$\small{O(M+N)}$，$\small{N}$是遍历 nums2，$\small{M}$是最后 res 转换为 vector。空间复杂度是$\small{O(N)}$。

力扣 454

  四数相加Ⅱ
  这个题目如果使用暴力解法，复杂度是$\small{O(N^4)}$。注意到题目要求nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0，也就是nums1[i] + nums2[j] == - nums3[k] - nums4[l]。那么可以两两一组，先遍历计算 nums1 和 nums2 元素的和，并建立map表（这里用map表是因为可以利用value统计相同元素出现的个数），然后再遍历寻找nums3 和 nums4 元素的和（取相反数）是否出现在map表中，如果出现将对应value值相加，最终就能够返回元组个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
{
    // 初始化table后table里面的value默认为0
    unordered_map<int, int> table;
    for(int& a : nums1)
    {
        for(int& b : nums2)
        {
            // 这里有两层含义，如果a + b在table中有相同的元素，value++，如果没有，那么table 自动添加a + b的值，并value++
            table[a + b]++;
        }
    }
    int count = 0;
    for(int& c : nums3)
    {
        for(int& d : nums4)
        {
            int target = -(c + d);
            if(table.find(target) != table.end())
                // 这里意思是返回指定key下的value
                count += table[target];
        }
    }
    return count;
}

  时间复杂度是$\small{O\left( N^2 \right)}$，空间复杂度是$\small{O\left( N^2 \right)}$。