题目链接

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例

示例1：

输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]

提示

  • 输出结果中的每个元素一定是唯一的。

  • 我们可以不考虑输出结果的顺序。

    思路

    思路1：排序+双指针

    将两个数组排序，维护两个指针，初始时指向两个数组头部，每次比较两个数字大小，同时还要比较是否重复。

    思路2：哈希表

    题目允许无序，不重复，因此我们可以使用 std::unorder_set 来完成这个题目。
    详细分析看基础知识。

    题解

    思路1：排序+双指针

    1. class Solution {
    2.  public:
    3.   vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4.       sort(nums1.begin(), nums1.end());
    5.       sort(nums2.begin(), nums2.end());
    6.       int i = 0, j = 0;
    7.       vector<int> ans;
    8.       while (i < (int)nums1.size() && j < (int)nums2.size()) {
    9.           if (nums1[i] == nums2[j]) {
    10.               if (0 == ans.size() || nums1[i] != ans.back()) {
    11.                   ans.emplace_back(nums1[i]);
    12.               }
    13.               ++i;
    14.               ++j;
    15.           } else if (nums1[i] < nums2[j]) {
    16.               ++i;
    17.           } else {
    18.               ++j;
    19.           }
    20.       }
    22.       return ans;
    23.   }
    24. };

    思路2：哈希表

    1. class Solution {
    2.  public:
    3.   vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4.       unordered_set<int> nums(nums1.begin(), nums1.end());
    5.       unordered_set<int> ans;
    6.       for (int num : nums2) {
    7.           if (nums.find(num) != nums.end()) {
    8.               ans.insert(num);
    9.           }
    10.       }
    11.       return vector<int>(ans.begin(), ans.end());
    12.   }
    13. };

    复杂度分析

    思路1：排序+双指针

  • 时间复杂度：0349-两个数组的交集 - 图1

  • 空间复杂度：0349-两个数组的交集 - 图2

    思路2：哈希表

  • 时间复杂度：0349-两个数组的交集 - 图3

  • 空间复杂度：0349-两个数组的交集 - 图4