两个数组的交集

题目描述

给定两个整数数组 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：理解问题核心

题目要求找到两个数组共有的元素，且结果中不能有重复元素。这意味着我们不仅需要判断一个元素是否同时在两个数组中出现，还需要对结果进行去重。

步骤2：选择数据结构

为了高效地查找和去重，哈希集合（HashSet）是理想的数据结构：

• 哈希集合：基于哈希表实现，支持平均 O(1) 时间的插入、删除和查找操作。
• 去重：集合本身不允许重复元素，自动满足题目对结果去重的要求。

步骤3：算法设计思路

1. 将第一个数组转换为集合：遍历 nums1，将所有元素存入一个哈希集合 set1。这一步自动去除了 nums1 中的重复元素。
2. 遍历第二个数组并检查：遍历 nums2，对于每个元素，检查它是否存在于 set1 中。
   • 如果存在，说明该元素是交集的一部分，将其加入结果集合 intersectionSet（另一个哈希集合，用于存储最终的交集元素）。
3. 返回结果：将 intersectionSet 转换为列表或数组作为最终输出。

为什么需要两个集合？

• set1：用于快速判断 nums2 中的元素是否在 nums1 中出现。
• intersectionSet：用于收集交集元素，并确保结果中无重复（虽然 nums2 可能有重复，但集合会自动去重）。

步骤4：详细步骤与示例

以 nums1 = [4,9,5], nums2 = [9,4,9,8,4] 为例：

1. 构建 set1：

   • 遍历 nums1：元素 4 → set1 = {4}；元素 9 → set1 = {4,9}；元素 5 → set1 = {4,9,5}。
   • set1 最终为 {4,9,5}。

2. 遍历 nums2 并构建交集集合：

   • 初始化 intersectionSet = {}（空集合）。
   • 遍历 nums2：
     • 元素 9：检查 9 in set1？是 → 加入 intersectionSet = {9}。
     • 元素 4：检查 4 in set1？是 → 加入 intersectionSet = {9,4}。
     • 元素 9：检查 9 in set1？是，但 9 已在 intersectionSet 中，集合自动去重，无变化。
     • 元素 8：检查 8 in set1？否 → 忽略。
     • 元素 4：检查 4 in set1？是，但 4 已在 intersectionSet 中，忽略。
   • intersectionSet 最终为 {9,4}。

3. 输出结果：将 intersectionSet 转换为列表，例如 [9,4]（顺序无关紧要）。

步骤5：复杂度分析

• 时间复杂度：O(m + n)，其中 m 和 n 分别是 nums1 和 nums2 的长度。遍历两个数组各一次，哈希集合的操作平均为 O(1)。
• 空间复杂度：O(min(m, n))。在最坏情况下（两数组无交集），set1 存储较小数组的所有元素，intersectionSet 存储交集（可能为空）。通常以较小数组的长度为基准。

步骤6：边界情况考虑

1. 空数组：如果其中一个数组为空，则交集为空。
2. 无交集：如 nums1 = [1,2], nums2 = [3,4]，结果应为空列表。
3. 大数组：哈希集合能高效处理大量数据，但需注意内存使用。

步骤7：代码实现（Python示例）

def intersection(nums1, nums2):
    # 将 nums1 转换为集合
    set1 = set(nums1)
    # 用于存储交集的集合
    intersection_set = set()
    
    # 遍历 nums2，检查元素是否在 set1 中
    for num in nums2:
        if num in set1:
            intersection_set.add(num)
    
    # 将集合转换为列表返回
    return list(intersection_set)

# 测试
nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
print(intersection(nums1, nums2))  # 输出 [9, 4] 或 [4, 9]

关键点总结

• 哈希集合的核心作用：利用其 O(1) 查找和自动去重的特性，高效解决交集问题。
• 去重的实现：通过两个集合分别去除输入数组和结果中的重复元素。
• 性能优势：相比暴力法（O(m*n)）或排序+双指针法（O(m log m + n log n)），哈希法在平均情况下具有最优的线性时间复杂度。

通过上述步骤，你可以清晰地理解如何利用哈希集合高效求解两个数组的交集问题。