两个数组的交集 题目描述 给定两个整数数组 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. 问题理解与目标分析 我们的目标是找出两个数组 共同拥有 的元素。这里有一个关键要求：结果中的每个元素必须是 唯一的 。这意味着即使一个元素在某个数组中出现了多次，在交集中也只出现一次。例如，示例1中，nums1 有两个2，nums2 有两个2，但交集结果是 [2] ，而不是 [2, 2] 。 所以，我们需要一个能够 快速判断一个元素是否存在 ，并且能 自动去重 的数据结构。哈希表（在许多编程语言中体现为集合 Set ）正是为这种场景设计的。 2. 核心思路 我们可以利用哈希集合（ HashSet ）来高效解决这个问题。基本思路分为两步： 第一步 - 存储与去重 ：将其中一个数组的所有元素存入一个哈希集合。这个过程会自动过滤掉该数组内部的重复元素。 第二步 - 查找与收集 ：遍历另一个数组，对于其中的每个元素，检查它是否存在于第一步创建的哈希集合中。如果存在，就说明它是交集元素，我们将其加入到结果集合中（为了再次确保结果不重复）。 3. 逐步推演 以示例2（nums1 = [ 4,9,5]， nums2 = [ 9,4,9,8,4 ]）为例： 步骤A：构建第一个数组的哈希集合 新建一个空的哈希集合 set1 ，用于存储 nums1 的元素。 遍历 nums1 ： 元素 4 ： set1 中没有4，将其加入。 set1 = {4} 元素 9 ： set1 中没有9，将其加入。 set1 = {4, 9} 元素 5 ： set1 中没有5，将其加入。 set1 = {4, 9, 5} 此时， set1 代表了 nums1 中所有 不重复 的元素。 步骤B：查找交集并去重 新建一个空的哈希集合 resultSet ，用于存放最终的交集结果（同样为了去重）。 遍历 nums2 ： 元素 9 ：检查 set1 中是否有 9 ？有！将 9 加入 resultSet 。 resultSet = {9} 元素 4 ：检查 set1 中是否有 4 ？有！将 4 加入 resultSet 。 resultSet = {9, 4} 元素 9 ：检查 set1 中是否有 9 ？有！但 resultSet 中已有 9 ，根据集合特性，重复添加无效。 resultSet 不变。 元素 8 ：检查 set1 中是否有 8 ？没有。忽略。 元素 4 ：检查 set1 中是否有 4 ？有！但 resultSet 中已有 4 ，忽略。 遍历结束， resultSet = {9, 4} 。 步骤C：格式转换 题目要求返回数组。我们只需要将 resultSet 这个集合转换为数组即可，例如 [9, 4] 或 [4, 9] 。 4. 算法复杂度分析 时间复杂度：O(m + n) ，其中 m 和 n 分别是两个数组的长度。我们分别对两个数组进行了一次线性遍历，而在哈希集合中进行插入和查找操作的平均时间复杂度是 O(1)。 空间复杂度：O(min(m, n)) 或 O(m+n)（取决于实现细节）。在最坏情况下，我们需要用一个哈希集合存储较小的那个数组的所有不重复元素，以及一个结果集合。在实际编码中，我们通常可以选择将较小的数组存入哈希集合，以优化空间复杂度。 5. 优化与变体 一个常见的空间优化是： 总是将较小的那个数组先放入哈希集合 。这样构建的哈希集合占用的空间更小。具体步骤调整为： 如果 nums1 的长度大于 nums2 的长度，则交换它们（或交换引用），确保我们总是用较小的数组来构建初始集合。 遍历较小的数组，将其元素存入哈希集合 smallSet 。 遍历较大的数组，对于每个元素，如果它在 smallSet 中，则将其加入 resultSet 。 6. 关键点总结 哈希集合是核心 ：它提供了 O(1) 时间复杂度的成员查询和自动去重功能，完美契合本题的两个需求：“快速判断是否存在”和“结果唯一”。 两步法 ：先“建集”，后“查集收果”，逻辑清晰。 空间优化 ：通过先处理较小数组，可以减少哈希集合的初始内存占用。 这个题目是哈希表（集合）最经典和直接的应用之一，它展示了如何利用哈希结构的高效查找特性来解决数据比较和过滤问题。