查阅更多的题解，请点击

Problem

349. Intersection of Two Arrays

Solution

注意题目要求的两数组的交集，是求两数组的相同元素，每个元素仅算一次

hash table, O(m+n) time

利用一个数组创建一个hash table，再遍历另一个数组，查找元素是否在hash table中出现

class Solution
{
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        unordered_set<int> keys(nums1.begin(), nums1.end());
        vector<int> res;
        for (auto num : nums2)
        {
            if (keys.count(num))
            {
                res.emplace_back(num);
                keys.erase(num);
            }
        }
        return res;
    }
};

sort & two pointers, O(max(m,n)logmax(m,n)) time

class Solution1
{
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> res;
        int i = 0, j = 0;
        while (i < nums1.size() && j < nums2.size())
        {
            if (nums1[i] > nums2[j])
            {
                j++;
            }
            else if (nums1[i] < nums2[j])
            {
                i++;
            }
            else
            {
                if (res.empty() || nums1[i] != res.back())
                {
                    res.emplace_back(nums1[i]);
                }
                i++;
                j++;
            }
        }
        return res;
    }
};

GitHub传送门