349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Note:

• Each element in the result must be unique.

• The result can be in any order.

Runtime: 4 ms, faster than 100.00% of C++ online submissions for Intersection of Two Arrays.

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.empty() || nums2.empty()) {
            return vector<int>();
        }
        unordered_set<int> set(nums1.begin(), nums1.end());
        vector<int> result;
        for (auto n: nums2) {
            if (set.erase(n) > 0) {
                result.push_back(n);
            }
        }
        return result;
    }
};

本题目主要考察的是搜索，通过 set 优化搜索的时间复杂度为 O(1)