题目描述

1. 考虑重复元素的交集

给你两个整数数组 nums1 和 nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（取较小值）。

2. 不考虑重复元素的交集

给定两个数组，返回它们的交集。输出结果中的每个元素一定是唯一的。

解题思路

1. 考虑重复元素（排序 + 双指针）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
    nums1.sort()  # 先排序
    nums2.sort()
    i, j = 0, 0   # 双指针
    res = []
    
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:     # 相等时添加到结果
            res.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:    # nums1当前值小，移动i
            i += 1
        else:                        # nums2当前值小，移动j
            j += 1
    return res

2. 不考虑重复元素（集合运算）

1
2
3
4
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    set1 = set(nums1)    # 转换为集合，自动去重
    set2 = set(nums2)
    return list(set1 & set2)    # 使用 & 运算符求交集

复杂度分析

考虑重复元素的解法

  • 时间复杂度：O(nlogn)，主要是排序的开销
  • 空间复杂度：O(min(n,m))，用于存储结果

不考虑重复元素的解法

  • 时间复杂度：O(n)，集合操作的时间
  • 空间复杂度：O(n)，用于存储集合

需要掌握的知识点

  1. 双指针技巧：

    • 双指针的移动策略
    • 如何处理有序数组

  2. 集合操作：

    • 集合的创建：set()
    • 集合的交集运算：&
    • 集合转列表：list()

  3. Python 语法：

    • 列表的排序：sort()
    • 列表的添加元素：append()
    • 集合的基本操作

  4. 算法思维：

    • 如何处理重复元素
    • 如何选择合适的数据结构