一、问题描述
给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素应该是唯一的，并且我们可以不考虑输出结果的顺序。
示例:
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]提示：
- 每个输入数组中只有一个数字。
- 两个数组不会有公共元素。
二、方案一：使用哈希集合
1、思路
使用哈希集合来解决这个问题。首先，我们将一个数组转换成哈希集合，然后遍历另一个数组，检查元素是否在哈希集合中。如果在，并且结果集中还没有这个元素，我们就将其添加到结果集中
2、代码实现
go
func intersection(nums1 []int, nums2 []int) []int {
set1 := map[int]bool{}
set2 := map[int]bool{}
for _, num := range nums1 {
set1[num] = true
}
for _, num := range nums2 {
set2[num] = true
}
result := []int{}
for num := range set1 {
if set2[num] {
result = append(result, num)
}
}
return result
}3、复杂度分析
- 时间复杂度：O(m + n)，其中 m 和 n 分别是两个数组的长度。
- 空间复杂度：O(m + n)，用于存储两个数组的哈希集合。
三、方案二：排序和双指针
1、思路
如果两个数组是有序的，我们可以使用双指针方法来找到它们的交集。首先，对两个数组进行排序，然后使用两个指针分别遍历两个数组。如果两个指针指向的元素相同，那么这个元素就是交集的一部分。如果不同，我们就移动指向较小元素的指针。
2、代码实现
go
func intersection(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
sort.Ints(nums2)
var res []int
i, j := 0, 0
for i < len(nums1) && j < len(nums2) {
if nums1[i] == nums2[j] {
// 去除重复元素
if len(res) == 0 || nums1[i] > res[len(res)-1] {
res = append(res, nums1[i])
}
i++
j++
} else if nums1[i] < nums2[j] {
i++
} else {
j++
}
}
return res
}3、复杂度分析
- 时间复杂度：O(m log m + n log n)，其中 m 和 n 分别是两个数组的长度，排序的时间复杂度是 O(log n)。
- 空间复杂度：O(1)，不需要额外的空间。
四、总结
| 方案 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 哈希集合 | O(m + n) | O(m + n) | 适用于数组无序或元素重复较多的情况 |
| 排序和双指针 | O(m log m + n log n) | O(1) | 适用于数组有序且元素重复较少的情况 |
根据数组的特性和对时间、空间复杂度的需求，可以选择合适的方案。