349 两个数组的交集

一、题目

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

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

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

二、题解

方法一：哈希表

思路：哈希表

1. 核心思路

因为题目要求返回两个数组的交集，并且结果中的元素必须是唯一的。

所以可以使用 HashSet：

  • 第一个 HashSet 用来存储 nums1 中的元素；
  • 第二个 HashSet 用来存储最终的交集结果，保证结果不重复。

2. 具体步骤

  1. 创建一个 HashSet，把 nums1 中的所有元素加入进去。
  2. 遍历 nums2：
    • 如果当前元素在第一个集合中出现过，说明它是交集元素；
    • 将它加入结果集合中。
  3. 将结果集合转换成数组返回。

3. 关键逻辑

if (set1.contains(num)) {
    resultSet.add(num);
}

解释：

  • set1.contains(num) 表示判断 nums2 中的当前元素是否在 nums1 中出现过；
  • 如果出现过，说明它是两个数组的交集元素；
  • 使用 resultSet.add(num) 可以自动去重。

4. 代码

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 1. 用 HashSet 存储 nums1 中的元素，自动去重
        Set<Integer> set1 = new HashSet<>();

        for (int num : nums1) {
            set1.add(num);
        }

        // 2. 用 HashSet 存储交集结果，保证结果唯一
        Set<Integer> resultSet = new HashSet<>();

        // 3. 遍历 nums2，判断当前元素是否在 nums1 中出现过
        for (int num : nums2) {
            if (set1.contains(num)) {
                resultSet.add(num);
            }
        }

        // 4. 将 HashSet 转换为 int[]
        int[] result = new int[resultSet.size()];
        int index = 0;

        for (int num : resultSet) {
            result[index++] = num;
        }

        return result;
    }
}

5. 复杂度分析

时间复杂度：O(m+n)O(m + n)

说明：其中 m 是 nums1 的长度，n 是 nums2 的长度。

我们遍历了一次 nums1，又遍历了一次 nums2。

空间复杂度：O(m+k)O(m + k)

说明：set1 最多存储 nums1 中的所有元素，resultSet 存储交集元素。

其中 k 是交集元素的个数。

方法二：排序 + 双指针

思路：排序 + 双指针

1. 核心思路

先将两个数组排序。

排序后，两个数组中的元素是有序的，因此可以使用两个指针分别遍历两个数组。

如果两个指针指向的元素相等，说明找到了交集元素。

如果不相等，就移动较小元素所在数组的指针。

2. 具体步骤

  1. 对 nums1 和 nums2 排序。
  2. 定义两个指针 i 和 j，分别指向两个数组的开头。
  3. 比较 nums1[i] 和 nums2[j]：
    • 如果相等，加入结果集合，然后两个指针都向后移动；
    • 如果 nums1[i] < nums2[j]，移动 i；
    • 如果 nums1[i] > nums2[j]，移动 j。
  4. 最后将结果集合转换成数组返回。

3. 关键逻辑

if (nums1[i] == nums2[j]) {
    resultSet.add(nums1[i]);
    i++;
    j++;
} else if (nums1[i] < nums2[j]) {
    i++;
} else {
    j++;
}

解释：

  • 如果两个数相等，说明找到了交集元素；
  • 如果 nums1[i] 更小，说明它不可能再和 nums2[j] 匹配，需要移动 i；
  • 如果 nums2[j] 更小，说明它不可能再和 nums1[i] 匹配，需要移动 j。

4. 代码

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 1. 先对两个数组排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        // 2. 定义两个指针
        int i = 0;
        int j = 0;

        // 3. 用 HashSet 存储结果，保证元素唯一
        Set<Integer> resultSet = new HashSet<>();

        // 4. 双指针遍历两个数组
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                // 找到交集元素
                resultSet.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                // nums1 当前元素较小，移动 i
                i++;
            } else {
                // nums2 当前元素较小，移动 j
                j++;
            }
        }

        // 5. 将 HashSet 转换为 int[]
        int[] result = new int[resultSet.size()];
        int index = 0;

        for (int num : resultSet) {
            result[index++] = num;
        }

        return result;
    }
}

5. 复杂度分析

时间复杂度：O(mlog⁡m+nlog⁡n)O(m \log m + n \log n)

说明：主要时间消耗在排序上，其中 m 是 nums1 的长度，n 是 nums2 的长度。

空间复杂度：O(k)O(k)

说明：resultSet 用来存储交集元素，其中 k 是交集元素的个数。

评论