题解 | #两个数组的交集#

题目链接

题目描述

给定两个整数序列 nums1 和 nums2，返回它们的交集。

要求:

输出结果中的每个元素一定是唯一的。
你还需要保证返回值需要按照升序排列。

这是一个 核心代码模式 (Core Code Mode) 的题目，你只需要实现 intersection 函数。

示例 1: 输入:

[1,1,4],[5,1,4]

输出:

[1,4]

解题思路

这道题要求我们找出两个数组的交集，并且结果需要去重和排序。这正是 哈希集合 (Hash Set) 的典型应用场景。

方法一：使用哈希集合

这个方法直观且高效，能很好地处理去重的要求。

算法步骤:

创建一个哈希集合 set1，并遍历第一个数组 nums1，将其所有元素添加到 set1 中。哈希集合会自动处理 nums1 内部的重复元素。
创建一个新的哈希集合 intersectionSet，用于存放最终的交集结果。
遍历第二个数组 nums2。对于 nums2 中的每一个元素 num，检查它是否存在于 set1 中。
如果 set1 包含 num，就将 num 添加到 intersectionSet 中。intersectionSet 同样会自动处理交集中的重复元素（例如，当 nums1 是 [1]，nums2 是 [1, 1] 时）。
遍历结束后，intersectionSet 中就包含了两个数组所有共有的、不重复的元素。
由于题目要求返回一个升序排列的数组，我们将 intersectionSet 转换为一个列表或数组，并对其进行排序。
返回排序后的结果。

方法二：排序 + 双指针

如果不能使用哈希集合，或者想要一个空间复杂度更优的解法，可以采用这个方法。

算法步骤:

对两个输入数组 nums1 和 nums2 分别进行升序排序。
初始化两个指针，p1 指向 nums1 的开头，p2 指向 nums2 的开头。
初始化一个空的结果列表 result。
当 p1 和 p2 都没有越界时，进行循环比较：
- 如果 nums1[p1] < nums2[p2]，说明 nums1[p1] 较小，不可能是交集元素，将 p1 右移。
- 如果 nums1[p1] > nums2[p2]，说明 nums2[p2] 较小，将 p2 右移。
- 如果 nums1[p1] == nums2[p2]，找到了一个交集元素。为了保证结果唯一，只有当这个元素与 result 中最后一个元素不同时，才将其加入 result。然后将 p1 和 p2 同时右移。
循环结束后，result 就是排好序的唯一交集。

本题解将采用更简洁、更符合哈希思想的 方法一，并展示 C++ STL 中更地道的 set_intersection 用法。同样，我们也会展示 Java 中使用现代 Stream API 的地道写法。

代码

cpp
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums1 int整型vector 
     * @param nums2 int整型vector 
     * @return int整型vector
     */
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // std::set 会自动排序并去重
        set<int> set1(nums1.begin(), nums1.end());
        set<int> set2(nums2.begin(), nums2.end());
        
        vector<int> result;
        // std::set_intersection 要求输入范围是有序的，set 完美满足
        // std::back_inserter 会将结果高效地插入到 vector 末尾
        set_intersection(set1.begin(), set1.end(), 
                         set2.begin(), set2.end(), 
                         back_inserter(result));
        
        return result;
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums1 int整型一维数组 
     * @param nums2 int整型一维数组 
     * @return int整型一维数组
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        // 1. 将 nums2 放入一个 Set 中，以便高效查找
        Set<Integer> set2 = Arrays.stream(nums2).boxed().collect(Collectors.toSet());
        
        // 2. 使用 Stream API 处理 nums1
        return Arrays.stream(nums1)
                     .distinct()       // 去除 nums1 自身的重复元素
                     .filter(set2::contains) // 筛选出也存在于 set2 中的元素 (求交集)
                     .sorted()         // 将结果排序
                     .toArray();        // 转换为数组
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums1 int整型一维数组 
# @param nums2 int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def intersection(self , nums1: List[int], nums2: List[int]) -> List[int]:
        # Python 的集合运算非常强大和简洁
        # set(nums1) & set(nums2) 直接计算出两个集合的交集
        return sorted(list(set(nums1) & set(nums2)))

算法及复杂度

算法: 哈希集合
时间复杂度: $\mathcal{O}(N + M + K \log K)$ ，其中 $N$ 和 $M$ 分别是两个数组的长度， $K$ 是交集的大小。 $\mathcal{O}(N)$ 用于构建第一个集合， $\mathcal{O}(M)$ 用于遍历第二个数组并查找， $\mathcal{O}(K \log K)$ 用于对结果进行排序。在 Python 的实现中，两个集合的交集操作 & 的时间复杂度是 $\mathcal{O}(N+M)$ ，所以总复杂度类似。
空间复杂度: $\mathcal{O}(N + K)$ 。 $\mathcal{O}(N)$ 用于存储第一个集合， $\mathcal{O}(K)$ 用于存储交集结果。