Leetcode 每日一题 两个数组的交集 （golang）

题目

排序

思路
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
}