Easy

题目描述

给定两个整数数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

示例 1：

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

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

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

解题思路

解题思路

这道题要求找出两个数组的交集，并且结果中每个元素唯一。我们有几种常见的解法：

方法一：哈希表法（推荐） 将第一个数组的所有元素存入哈希集合中去重，然后遍历第二个数组，如果元素在哈希集合中存在，就加入结果集合。这种方法时间复杂度最优。

方法二：双指针法 先对两个数组进行排序，然后使用双指针分别指向两个数组的开头，比较指针所指元素的大小关系来移动指针，相等时记录交集元素。

方法三：内置集合运算 利用编程语言提供的集合数据结构，直接进行集合求交运算，代码最简洁。

从时间复杂度角度考虑，哈希表法是最优的，平均情况下为 O(m+n)。排序方法的时间复杂度为 O(mlogm + nlogn)。这里我们采用哈希表方法作为主要实现。

代码实现

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> result;
        
        for (int num : nums2) {
            if (set1.count(num)) {
                result.insert(num);
            }
        }
        
        return vector<int>(result.begin(), result.end());
    }
};

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        result = set()
        
        for num in nums2:
            if num in set1:
                result.add(num)
        
        return list(result)

public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        HashSet<int> set1 = new HashSet<int>(nums1);
        HashSet<int> result = new HashSet<int>();
        
        foreach (int num in nums2) {
            if (set1.Contains(num)) {
                result.Add(num);
            }
        }
        
        return result.ToArray();
    }
}

var intersection = function(nums1, nums2) {
    const set1 = new Set(nums1);
    const result = new Set();
    
    for (const num of nums2) {
        if (set1.has(num)) {
            result.add(num);
        }
    }
    
    return Array.from(result);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表法排序+双指针法
时间复杂度O(m+n)O(mlogm + nlogn)
空间复杂度O(min(m,n))O(1)

其中 m 和 n 分别是两个数组的长度。哈希表法空间复杂度取决于较小数组的大小，排序法的空间复杂度为常数（不考虑排序的额外空间）。

相关题目