华为 OD 训练营 · 题解精讲
LC349. 两个数组的交集
LC349. 两个数组的交集 视频地址。
题目描述
给定两个数组 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
题目解析
解题思路
本题要求两个数组的交集，且结果元素唯一。参考代码采用排序 + 双指针的方法：先将两个数组分别排序，然后使用两个指针分别遍历，通过比较当前元素大小来同步移动指针，遇到相等元素且不重复时加入结果。
数据结构：使用列表存储结果，利用排序后相邻元素不重复的特性去重。
关键步骤
1. 排序：对 nums1 和 nums2 分别升序排序。 2. 双指针遍历：
- 初始化
index1 = 0，index2 = 0。 - 循环条件：两个指针均未越界。
- 比较
nums1[index1]与nums2[index2]： - 相等：若结果列表为空或当前值不等于列表最后一个元素（避免重复），则加入结果；然后两指针同时右移。
- 小于：
nums1当前值较小，不可能与nums2后续元素相等，右移index1。 - 大于：
nums2当前值较小，右移index2。
示意图（以 nums1=[1,2,2,1]，nums2=[2,2] 为例）：
排序后：
nums1: [1,1,2,2]
nums2: [2,2]
初始：index1=0(1), index2=0(2)
1<2 → index1=1(1)
1<2 → index1=2(2)
2==2 → 加入2，index1=3(2), index2=1(2)
2==2 → 但res[-1]==2，不重复加入，index1=4, index2=2 → 结束
结果：[2]复杂度分析
- 时间复杂度：O(m log m + n log n)，其中 m、n 为两数组长度。排序占主导，双指针遍历 O(m+n) 较小。
- 空间复杂度：O(log m + log n)，排序所需的递归栈空间（Python 的 Timsort 为 O(log n)）。结果列表不计入额外空间。
参考代码
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 首先对两个数组进行排序
nums1.sort()
nums2.sort()
# 计算出两个数组的长度
length1 = len(nums1)
length2 = len(nums2)
# 两个数组的交集结果数组长度必然是小于等于最短数组的长度
res = list()
# 设置三个索引指针
# index 指向结果数组 res ，每当 index 指向的位置填充了元素就向后移动
# index = 0
# index1 指向数组 nums1 中的元素，将该元素和 index2 指向数组 nums2 中的元素进行比较
index1 = 0
# index2 指向数组 nums2 中的元素，将该元素和 index1 指向数组 nums1 中的元素进行比较
index2 = 0
# 移动 index1 和 index2
while index1 < length1 and index2 < length2 :
# 获取 index1 指向的元素值
num1 = nums1[index1]
# 获取 index2 指向的元素值
num2 = nums2[index2]
# num1 和 num2 的大小关系有三种
# 1、num1 == num2
if num1 == num2 :
# 由于输出结果中的每个元素一定是 【唯一】 的，所以要做一下判断
# 如果 res 中的 index 在起始位置，说明还没有存放元素
# 那么这个相等的元素可以存放到 res 中
# 如果 res 中的 index 不在起始位置
# 当它前面存放的元素并不是现在想要存放的元素
# 那么这个相等的元素可以存放到 res 中
if not res or num1 != res[-1]:
res.append(num1)
# 移动 index1 ，比较其它元素
index1 += 1
# 移动 index2 ，比较其它元素
index2 += 1
# 2、num1 < num2
elif num1 < num2 :
# 由于两个数组已经排序了，说明此时 num1 肯定会小于 nums2 数组中 num2 后面所有的数
# 那 num1 肯定是无法在 nums2 中找到相等的元素
# 移动 index1 ，比较其它元素
index1 += 1
# 3、num1 > num2
else:
# 由于两个数组已经排序了，说明此时 num2 肯定会小于 nums1 数组中 num1 后面所有的数
# 那 num2 肯定是无法在 nums1 中找到相等的元素
# 移动 index2 ，比较其它元素
index2 += 1
# 最后返回结果数组中有值的那些元素就行
return res
时空复杂度
时间复杂度：O(mlogm+nlogn)。两数组快排时间复杂度分别是O(mlogm)、O(nlogn)，双指针遍历需要O(m+n)，复杂度取决于较大的O(mlogm+nlogn)。
空间复杂度：O(logm+logn)。排序使用的额外空间。