解法I 哈希表

func intersect(nums1 []int, nums2 []int) []int {
    var result []int
    hashTable := make(map[int]int)

    for i := range nums1{
        if _,ok:=hashTable[nums1[i]];!ok{
            hashTable[nums1[i]] = 1
        }else{
            hashTable[nums1[i]] = hashTable[nums1[i]] + 1
        }
    }

    for j := range nums2{
         if v,ok:=hashTable[nums2[j]];ok&&v>0{
            result = append(result,nums2[j])
            hashTable[nums2[j]] = hashTable[nums2[j]]-1
         }
    }
    
    return result
    
}

时间复杂度

假设表里nums1长度为m nums2长度为 n,需要遍历这两个数组
O(m+n)

空间复杂度

O(min(m,n))

解法II 排序➕双指针法

如果两个数组是有序的，则可以便捷地计算两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

import "sort"
func intersect(nums1 []int, nums2 []int) []int {
    sort.Ints(nums1)
    sort.Ints(nums2)
    length1, length2 := len(nums1), len(nums2)
    index1, index2 := 0, 0

    intersection := []int{}
    for index1 < length1 && index2 < length2 {
        if nums1[index1] < nums2[index2] {
            index1++
        } else if nums1[index1] > nums2[index2] {
            index2++
        } else {
            intersection = append(intersection, nums1[index1])
            index1++
            index2++
        }
    }
    return intersection
}

时间复杂度

O(mlog⁡m+nlog⁡n)O(mlog m+nlog n)O(mlogm+nlogn)，其中 mmm 和 nnn 分别是两个数组的长度。对两个数组进行排序的时间复杂度是 O(mlog⁡m+nlog⁡n)O(mlog m+nlog n)O(mlogm+nlogn)，遍历两个数组的时间复杂度是 O(m+n)O(m+n)O(m+n)，因此总时间复杂度是 O(mlog⁡m+nlog⁡n)O(mlog m+nlog n)O(mlogm+nlogn)。

空间复杂度

O(min⁡(m,n))O(min(m,n))O(min(m,n))，其中 mmm 和 nnn 分别是两个数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。不过在 C++ 中，我们可以直接创建一个 vector，不需要把答案临时存放在一个额外的数组中，所以这种实现的空间复杂度为 O(1)O(1)O(1)。

部分参考:

1. 官方题解