跳转至

349 两个数组的交集

leetcode

哈希表

数组

本题后面 力扣改了 题目描述 和 后台测试数据,增添了 数值范围:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

所以就可以 使用数组来做哈希表了, 因为数组都是 1000以内的。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 对答案去重
        unordered_set<int> ans;
        int hashMap[1005] = {0};
        for (int num : nums1) {
            hashMap[num] = 1;
        }
        for (int num : nums2) {
            if (hashMap[num] == 1)
                ans.insert(num);
        }
        return vector<int>(ans.begin(), ans.end());
    }
};

unordered_set

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> ans;
        unordered_set<int> hashMap;
        for(int num : nums1){
            hashMap.insert(num);
        }
        for(int num : nums2){
            if(hashMap.find(num) != hashMap.end())
                ans.insert(num);
        }
        return vector<int>(ans.begin(),ans.end());
    }
};

复杂度分析:

  • 时间复杂度: \(O(n)\)
  • 空间复杂度: \(O(n)\)