当前位置：首页 > news >正文

LeetCode题练习与总结：两个数组的交集--349

news 2025/4/21 11:52:50

一、题目描述

给定两个数组 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 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

二、解题思路

使用两个集合（HashSet）来解决这个问题。集合的特点是元素不重复，这可以帮助我们找到两个数组的交集，并且保证交集中的元素是唯一的。
首先遍历第一个数组 nums1，将其所有元素添加到第一个集合 set1 中。
然后遍历第二个数组 nums2，对于 nums2 中的每个元素，检查它是否存在于 set1 中。如果存在，说明这个元素是两个数组的交集元素，将其添加到另一个集合 resultSet 中。
最后，将 resultSet 转换为数组，并返回。

三、具体代码

import java.util.HashSet;
import java.util.Set;class Solution {public int[] intersection(int[] nums1, int[] nums2) {// 创建两个HashSet用于存储元素Set<Integer> set1 = new HashSet<>();Set<Integer> resultSet = new HashSet<>();// 将nums1的元素添加到set1中for (int num : nums1) {set1.add(num);}// 遍历nums2，检查每个元素是否在set1中for (int num : nums2) {if (set1.contains(num)) {resultSet.add(num); // 如果在set1中，添加到结果集中}}// 将结果集转换为数组int[] result = new int[resultSet.size()];int i = 0;for (int num : resultSet) {result[i++] = num;}return result;}
}

这段代码实现了上述解题思路，并且能够处理题目中的示例情况。由于集合不允许重复元素，所以最终得到的交集数组中的元素都是唯一的。

四、时间复杂度和空间复杂度

1. 时间复杂度

遍历数组 nums1 并将其元素添加到集合 set1 中，这个操作的时间复杂度是 O(n)，其中 n 是 nums1 的长度。
遍历数组 nums2 并检查每个元素是否在集合 set1 中，这个操作的时间复杂度是 O(m)，其中 m 是 nums2 的长度。由于集合的 contains 方法的时间复杂度是 O(1)，所以整个循环的时间复杂度是 O(m)。
将结果集合 resultSet 转换为数组，这个操作的时间复杂度是 O(k)，其中 k 是结果集合的大小。

综合以上步骤，总的时间复杂度是 O(n + m + k)。由于 k 最多等于较小的输入数组的长度，因此时间复杂度可以简化为 O(n + m)。

2. 空间复杂度

集合 set1 的大小最多是 nums1 的长度，所以空间复杂度是 O(n)。
集合 resultSet 的大小最多是较小的输入数组的长度，因此空间复杂度是 O(min(n, m))。
结果数组 result 的大小与 resultSet 相同，所以空间复杂度也是 O(min(n, m))。

综合以上步骤，总的空间复杂度是 O(n + min(n, m))。由于 min(n, m) 不会超过 n，所以空间复杂度可以简化为 O(n)。

五、总结知识点

类定义：
- class 关键字用于定义一个类。
- Solution 是类的名称。
方法定义：
- public 关键字表示该方法可以被外部访问。
- int[] 表示该方法返回一个整数数组。
- intersection 是方法的名称。
- int[] nums1, int[] nums2 是方法的参数列表，表示该方法接受两个整数数组作为输入。
集合的使用：
- HashSet 是一个实现了 Set 接口的类，用于存储不包含重复元素的集合。
- Set<Integer> 表示集合中存储的是整数类型的元素。
集合的添加操作：
- add() 方法用于向集合中添加元素。
集合的查找操作：
- contains() 方法用于检查集合中是否包含某个元素。
增强型 for 循环：
- 用于遍历数组或集合中的每个元素。
数组的创建与初始化：
- int[] result = new int[resultSet.size()] 创建了一个新的整数数组，其大小与 resultSet 集合的大小相同。
数组的索引操作：
- 使用索引 i 来访问数组中的元素，并进行赋值操作 result[i++] = num。
方法返回值：
- return 关键字用于返回方法的结果。
变量声明与初始化：
- int i = 0 声明了一个整型变量 i 并初始化为 0。
集合与数组的转换：
- 将集合 resultSet 中的元素逐个赋值到数组 result 中。