求解两个数组的交集问题有很多种写法，这里主要介绍两种方法。还有其他的编程语言特色的求解方法。

题目描述

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

 

示例 1：

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

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

 

说明：

• 输出结果中的每个元素一定是唯一的。
• 我们可以不考虑输出结果的顺序。

方法一（借助哈希）

解题思路

要求解两个数组中的交集，首先我们可以去除掉各自列表中的重复元素。去除重复元素这一过程，可以使用set()集合的性质（不能存储重复元素）进行操作。

得到精简后的数组后，就可以进行元素级别的比较了。遍历长度较小的数组，然后在另一个数组中查找是否存在其中。这种方法有点还是可以有提升的地方。我们可以将查找的时间复杂度降低。即使用Hash来查找。所以在上一步的操作中，可以使用Java的HashSet()去重的同时，来减少查找的时间复杂度。

最后一步，定义一个结果变量，如果较短数组中的元素在另外一个数组中，则可以直接将元素添加到结果变量中，直到遍历完整个较短数组。

代码实现

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1 = set(nums1)
        nums2 = set(nums2)
        if len(nums1) < len(nums2):
            return [x for x in nums1 if x in nums2]
        else:
            return [x for x in nums2 if x in nums1]

复杂度分析

• 时间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要 O(m+n) 的时间，遍历较小的集合并判断元素是否在另一个集合中需要 O(min(m,n)) 的时间，因此总时间复杂度是 O(m+n)。

• 空间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度。空间复杂度主要取决于两个集合。

方法二（排序+双指针）

解题思路

这种方法的解题思路就比较直接了。借助合并两个有序链表的思想，设置两个指针i和j分别指向两个数组nums1和nums2，如果nums1[i] == nums2[j]那么就是两个列表的交集元素。将元素放到无重复元素的set()中。两个元素不相等的情况下，元素小的那个指针往前移一位，直到两个指针越界。

代码实现

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        res = set()
        i, j = 0, 0
        while i<len(nums1) and j<len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            elif nums1[i] == nums2[j]:
                res.add(nums1[i])
                i += 1
                j += 1
        return res

复杂度分析

• 时间复杂度：O(nlogn)，其中 m 和 n 分别是两个数组的长度。排序的时间复杂度级别是 O(nlogn)，双指针寻找交集元素的时间复杂度级别是 O(n)，因此总时间复杂度是 O(nlogn)。

• 空间复杂度：O(n)，其中 n 是数组的长度。在最坏的情况下，两数组的元素都一样。

其他代码示例

Python & 运算符

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

Python语言中的&运算符可以直接求出两列表的交集

Java retainAll()方法

public int[] intersection(int[] nums1, int[] nums2) {
    HashSet<Integer> set1 = new HashSet<>();
    HashSet<Integer> set2 = new HashSet<>();
    List<Integer> list = new ArrayList<>();
    for(int i:nums1){
        list.add(i);
    }
    for(int i:nums2){
        set2.add(i);
    }
    list.retainAll(set2);
    set1.addAll(list);
    return set1.stream().mapToInt(i->i).toArray();
}

A.retainAll(B)方法的含义：移除A中，不包含在B中的元素。