【LeetCode Cookbook（C++ 描述）】一刷哈希表（Hash Table）（下）

本系列文章仅是 GitHub 大神 @halfrost 的刷题笔记 《LeetCode Cookbook》的提纲以及示例、题集的 C++转化。原书请自行下载学习。
本篇文章涉及新手应该优先刷的几道经典哈希表算法题，分两篇文章，以后会更新“二刷”“三刷”等等。

LeetCode #349：Intersection of Two Arrays 两个数组的交集

给定两个数组，计算它们的交集。

实际上，就是查找 nums2 的元素是否在 nums1 中，只要是从一堆数中查找一个数，那么均可以考虑哈希查找，而对于未知数目与数值的情况，我们使用 unordered set 来解决。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> num_set(nums1.begin(), nums1.end());   //使用 nums1 初始化哈希集合
        vector<int> res;
        //遍历 nums2，检查元素是否在哈希集合中
        for (int num : nums2) {
            if (num_set.count(num)) {   //如果元素在哈希集合中，则添加到结果列表中
                res.push_back(num);
                num_set.erase(num);     //确保交集元素不会重复
            }
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

由于使用了内置的库函数，该算法效率并不高。我们可以直接使用哈希表构建所谓的“集合”，提高代码执行效率：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int>result;
        unordered_map<int ,int>hash;

        for(const auto &num : nums1) hash[num] = 1;
        for(const auto &num : nums2) {
            --hash[num];

            if(hash[num] == 0) result.push_back(num);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode #383：Ransom Note 赎金信

给定一个赎金信（ ransomNote ）字符串和一个杂志（ magazine ）字符串。

判断 ransomNote 能不能由 magazine 里的字符串构成。可以返回 true ，否则返回 false 。

类似于上篇文章的 #242 有效字母异位词，找出哈希函数 f(key) = key - 'a' ，对应出每个字母在哈希表中的索引，随后以 vector 类模拟哈希表：

• 遍历 magazine 字符串，哈希表中对应的字符增加。
• 遍历 ransomNote 字符串，自减哈希表中对应的字符，如果在自减之后该位置的值小于 0，则说明 magazine 中没有足够的字符构建 ransomNote ，直接返回 false 。
• 遍历结束，返回 true 。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.size() > magazine.size()) return false;  // ransomNote 长度过长，必然不满足题意

        vector<int> cnt(26);  //初始化含有 26 个元素的哈希函数
        for (auto & c : magazine) cnt[c - 'a']++;  //遍历 magazine，每个字符加入哈希表

        for (auto & c : ransomNote) {
            cnt[c - 'a']--;
            if (cnt[c - 'a'] < 0) return false;
        }

        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode #454：4Sum II - 四数相加 II

给定 4 个长度为 n 的整数数组，计算有多少个元组（ i , j , k , l ）能满足：

nums[i] + nums[j] + nums[k] + nums[l] == 0 。

这道题与上篇文章提及的 4Sum 问题是基本一致的，但是我们在这里尝试使用哈希查找解决。之前我们使用哈希查找解决 3Sum 问题只是为了练习哈希表的使用，然而这一问题则体现出哈希查找的优势。

思路大致如下：

• 初始化哈希表。
• 分组：nums1 和 nums2 一组，nums3 和 nums4 一组。
• 分别对 nums1 和 nums2 进行遍历，将所有 nums1 和 nums2 的值之和作为哈希表的 key ，和的次数作为哈希表的 value 。
• 分别对 nums3 和 nums4 进行遍历，若 -(nums1[k] + nums4[l]) 在哈希表中，则将对应的值累加进答案。

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> countAB;
        for (int u : A) for (int v : B) ++countAB[u + v];  //统计两个数组中的元素之和，同时统计出现的次数，放入 map

        int ans = 0;
        //统计剩余的两个元素的和，在 map 中找是否存在相加为 0 的情况，同时记录次数
        for (int u : C) for (int v : D) if (countAB.count(-u - v)) ans += countAB[-u - v];

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

以空间换时间，该算法的时间复杂度、空间复杂度均为$O(n^2)$ 。