题目

在这里插入图片描述

排序

思路
1.首先明确如果两个数组是有序的,那么有利于求交集
2.对两个数组排序,并对其遍历
3.把相同元素放在第三个数组中,直到一个数组遍历完

代码

func intersect(nums1 []int, nums2 []int) []int {
	sort.Ints(nums1)
	sort.Ints(nums2)  //对两数组排序
	res := []int{}    //创建第三个数组
	i,j := 0,0
	for i < len(nums1) && j < len(nums2) {
		if nums1[i] < nums2[j] {      //如果两个元素不相同,对小元素所在数组后一位遍历
				i++
		}else if nums1[i] > nums2[j] {
				j++                     //如果两个元素不相同,对大元素所在数组后一位遍历
		}else {
				res = append(res,nums1[i])    //判断两个数组中的相同元素,将相同元素添加到第三个数组中,并将两个数组向右一位移动
				i++
				j++      
		}
	}
	return res
}

当然也可以用双指针实现
1.初始时,两个指针分别指向两个数组的头部。
2.每次比较两个指针指向的两个数组中的数字,如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,将该数字添加到答案,并将两个指针都右移一位。
3.当至少有一个指针超出数组范围时,遍历结束。

写法相似

哈希表

思路
1.由于同一个数字在两个数组中都可能出现多次,因此需要用哈希表存储每个数字出现的次数。
2.首先遍历第一个数组,并在哈希表中记录第一个数组中的每个数字以及对应出现的次数,然后遍历第二个数组,对于第二个数组中的每个数字,如果在哈希表中存在这个数字,则将该数字添加到答案,并减少哈希表中该数字出现的次数。

代码

func intersect(nums1 []int, nums2 []int) []int {
    if len(nums1) > len(nums2) {
        return intersect(nums2, nums1)  //获取两个数组中的全部记录
    }
    m := map[int]int{}
    for _, num := range nums1 {
        m[num]++               //遍历较长数组,并记录各元素出现次数
    }

    res := []int{}
    for _, num := range nums2 {
        if m[num] > 0 {
            res = append(res, num)    //遍历较短数组,如果出现的元素次数大于0,将其放到第三个数组中
            m[num]--
        }
    }
    return res
}