力扣-349题两个数组的交集（C++）- 哈希

末蓝、 2022-09-07 14:37 147阅读 0赞

题目链接：[https://leetcode-cn.com/problems/intersection-of-two-arrays/][https_leetcode-cn.com_problems_intersection-of-two-arrays]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
**注：**  
1、使用数组来做哈希的题目，是因为题目都限制了数值的大小；而这道题目没有限制数值的大小，无法使用数组来做哈希表。如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。  
2、遇到哈希问题直接都用set，不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

解法一：

class Solution {
        
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        
            vector<int> result;
            unordered_set<int> element;
    
            for(auto& num1:nums1)
                if(element.count(num1)==0) element.insert(num1);
            
            for(auto& num2:nums2)
                if(element.count(num2)!=0){
        
                    element.erase(num2);
                    result.push_back(num2);
                }
            
            return result;
            
        }
    };

解法二：

class Solution {
        
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        
            unordered_set<int> result_set; // 存放结果
            unordered_set<int> nums_set(nums1.begin(), nums1.end());
            for (int num : nums2) {
        
                // 发现nums2的元素 在nums_set里又出现过
                if (nums_set.find(num) != nums_set.end()) {
        
                    result_set.insert(num);
                }
            }
            return vector<int>(result_set.begin(), result_set.end());
        }
    };

[https_leetcode-cn.com_problems_intersection-of-two-arrays]: https://leetcode-cn.com/problems/intersection-of-two-arrays/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/fc6cda8cdd064b929b99a24ad15d052a.png