golang leetcode349两个数组的交集 map 双指针+排序

两个数组的交集 leetcode349

使用map

由于golang中没有set，这里算是模拟的一种方式
当然这里也可以用数组来代替map

// 最简易的方式
func intersection(nums1 []int, nums2 []int) []int {
	table := make(map[int]int)

	result := []int{}

	for _, i2 := range nums1 {
		table[i2] = 1
	}
	for _, i2 := range nums2 {
		if table[i2] == 1 {
			table[i2] = 0
			result = append(result, i2)
		}

	}
	return result
}

排序+双指针

对数组进行排序后，就可以通过双指针的方式从小到大开始比较两个数组
以下两种方法都是采取的这个思路，只是循环的方式不同，复杂度相同

// 排序+双指针
func intersection(nums1 []int, nums2 []int) []int {
	index1, index2 := 0, 0

	sort.Ints(nums1)
	sort.Ints(nums2)

	L1 := len(nums1)
	L2 := len(nums2)

	result := []int{}

	for index1 < L1 {

		//当出现不是等于的情况时直接for循环
		for nums1[index1] < nums2[index2] {
			index1++
			if index1 >= L1 {
				return result
			}
		}

		for nums1[index1] > nums2[index2] {
			index2++
			if index2 >= L2 {
				return result
			}
		}

		if nums1[index1] == nums2[index2] {
			result = append(result, nums1[index1])
			for nums1[index1] == nums2[index2] {
				index2++
				if index2 >= L2 {
					return result
				}
			}
		}
	}
	return result

}

func intersection(nums1 []int, nums2 []int) (res []int) {
    sort.Ints(nums1)
    sort.Ints(nums2)
    for i, j := 0, 0; i < len(nums1) && j < len(nums2); {
        x, y := nums1[i], nums2[j]
        if x == y {
            if res == nil || x > res[len(res)-1] {
                res = append(res, x)
            }
            i++
            j++
        } else if x < y {
            i++
        } else {
            j++
        }
    }
    return
}