0349. 两个数组的交集 #
- 标签:数组、哈希表、双指针、二分查找、排序
- 难度:简单
题目大意 #
描述:给定两个数组 nums1
和 nums2
。
要求:返回两个数组的交集。重复元素只计算一次。
说明:
- $1 \le nums1.length, nums2.length \le 1000$。
- $0 \le nums1[i], nums2[i] \le 1000$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:哈希表 #
- 先遍历第一个数组,利用哈希表来存放第一个数组的元素,对应字典值设为
1
。 - 然后遍历第二个数组,如果哈希表中存在该元素,则将该元素加入到答案数组中,并且将该键值清空。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。
思路 2:分离双指针 #
- 对数组
nums1
、nums2
先排序。 - 使用两个指针
left_1
、left_2
。left_1
指向第一个数组的第一个元素,即:left_1 = 0
,left_2
指向第二个数组的第一个元素,即:left_2 = 0
。 - 如果
nums1[left_1]
等于nums2[left_2]
,则将其加入答案数组(注意去重),并将left_1
和left_2
右移。 - 如果
nums1[left_2]
小于nums2[left_2]
,则将left_1
右移。 - 如果
nums1[left_2]
大于nums2[left_2]
,则将left_2
右移。 - 最后输出答案数组。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。