349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 而不是【2，2】

思路一：哈希法，

时间复杂度O（m+n）,空间O（m+n）

  1. //哈希判断
  2. func intersection(nums1 []int, nums2 []int ) []int {
  3.     hash_m := map[int]bool{}         //1,定义哈希存储de真假
  4.     res := []int{}
  6.     for _, num1 := range nums1 {
  7.         hash_m[num1] = true          //2,第一个数组全部进哈希表
  8.     }
  10.     for _,num2 := range nums2 {
  11.         if hash_m[num2] == true {    //3,如果第二个数组有数字，和哈希表存的相同，就把此值取出哈希表，
  12.             hash_m[num2] = false     //否则继续加入表
  13.             res = append(res, num2)     //4,取出的数字加入res数组
  14.         }
  15.     }
  16.     return res
  17. }

思路二：排序+双指针

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 pre 表示上一次加入答案数组的元素。
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 pre ，将该数字添加到答案并更新 pre 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

解题思路
对两个数组排序后，采用归并算法双指针的思路
如果两个值不相等，则小的往后移动一位；找到相等的值，记起来，两个指针往后移动一位
满足元素的唯一性：找到相等值时，目标数组回溯一位，看看此元素是否已存在（因为已排序了，相同的元素肯定是连续的）

复杂度分析

  • 时间复杂度：(m_log_m+n_log_n)，其中 m 和 n 分别是两个数组的长度。对两个数组排序的时间复杂度分别是 O(m_log_m) 和 O(n_log_n)，双指针寻找交集元素的时间复杂度是 O(m+n)比较小，取大的，因此总时间复杂度是 O(m_log_m+n_log_n)。

  • 空间复杂度：O(logm+logn)，其中 m 和 n 分别是两个数组的长度。空间复杂度主要取决于排序使用的额外空间。

    //排序+双指针
func intersection(nums1 []int, nums2 []int) []int {
  sort.Ints(nums1)
  sort.Ints(nums2)

  res := make([]int, len(nums1))
  pre1, pre2, index := 0, 0, 0

  for pre1 < len(nums1) && pre2 < len(nums2) {
      if nums1[pre1] < nums2[pre2] {
          pre1++                                            //数值小的，指针向后一位
      }else if nums1[pre1] > nums2[pre2] {
          pre2++
      }else if index  > 0 && nums1[pre1] == res[index-1] {        //若有两个相同，回溯一位
          pre1++
          pre2++

      } else{
          res[index] = nums1[pre1]                        //记录重复值，存储res数组
          index++
          pre1++
          pre2++
      }
  }
  return res[0: index]
}