350 两个数组的交集 II

题目链接

350. 两个数组的交集 II

分析

使用哈希表对任一数组进行计数，遍历另一个数组时寻找交集即可

对于进阶问题：

如果数组有序，使用双指针可以一次遍历，并且不使用额外空间

将较小的数组做成哈希表可获得更小的空间复杂度

将 $nums1$ 做成哈希表，开个缓冲区遍历 $nums2$

代码实现

哈希表

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        unordered_map<int, int> um;
        for(int& i : nums1) {
            um[i]++;
        }
        for(int& i : nums2) {
            if(um[i] > 0) {
                ans.emplace_back(i);
                um[i]--;
            }
        }
        return ans;
    }
};

双指针

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        ranges::sort(nums1);
        ranges::sort(nums2);
        vector<int> ans;
        for(int i = 0, j = 0; i < nums1.size() && j < nums2.size(); ) {
            if(nums1[i] == nums2[j]) {
                ans.emplace_back(nums1[i]);
                i++, j++;
            } else if(nums1[i] > nums2[j]) {
                j++;
            } else {
                i++;
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$，使用双指针则为 $O(1)$