350、两个数组的交集

;(function () {
  /**
   * 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。
   * 返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
   */
  function intersect(nums1: number[], nums2: number[]): number[] {
    // 方法一
    // let res: number[] = [];
    // let len1 = nums1.length;
    // let len2 = nums2.length;
    // nums2.forEach(x => {
    //     if (nums1.indexOf(x) !== -1) {
    //         res.push(x);
    //         nums1.splice(nums1.indexOf(x), 1)
    //     }
    // })
    // return res

    // 方法二：哈希
    // type stringKey = {
    //     [key: string]: number
    // }
    // let res: number[] = [];
    // let len1 = nums1.length;
    // let len2 = nums2.length;
    // let obj: stringKey = {};
    // if (len1 > len2) {
    //     // 存储：短数组中元素的出现个数
    //     nums2.forEach(x => {
    //         obj[x] ? obj[x]++ : obj[x] = 1;
    //     })
    //     // 遍历长数组：obj中有某个相同元素，则个数减一（同时将该元素push到res数组中）
    //     nums1.forEach(x => {
    //         obj[x] ? (res.push(x) && obj[x]--) : null
    //     })
    // } else {
    //    nums1.forEach(x => {
    //         obj[x] ? obj[x]++ : obj[x] = 1;
    //     })
    //     nums2.forEach(x => {
    //         obj[x] ? (res.push(x) && obj[x]--) : null
    //     })
    // }
    // return res

    // 方法三：排序 + 双指针
    let res: number[] = []
    let p1 = 0,
      p2 = 0
    let cur
    let len1 = nums1.length,
      len2 = nums2.length
    // 1. 排序
    nums1.sort((a, b) => a - b)
    nums2.sort((a, b) => a - b)
    // 2. 双指针遍历：
    // 思路：（核心：相等的话指针同时移，谁小谁的指针就向后移动）
    // a. p1 === p2，则 p1👆   p2👆
    // b. p1 > p2 ，则 p2 👆
    // c. p1 < p2 ，则 p1 👆
    while (p1 < len1 && p2 < len2) {
      if (nums1[p1] === nums2[p2]) {
        res.push(nums1[p1++])
        p2++
      } else if (nums1[p1] > nums2[p2]) {
        p2++
      } else {
        p1++
      }
    }
    return res
  }
  let nums1 = [1, 2, 7, 1, 4, 3, 5, 6, 8]
  let nums2 = [3, 1, 1, 6]
  console.log(intersect(nums1, nums2))

  // 进阶：===================================
  // 如果给定的数组已经排好序呢？你将如何优化你的算法？
  // 如果 nums1 的大小比 nums2 小，哪种方法更优？
  // 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
})()