「每日LeetCode」2020年11月2日

本文最后更新于：2023年3月19日 晚上

Lt349.两个数组的交集

349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。
 示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

说明：

  • 输出结果中的每个元素一定是唯一的。
  • 我们可以不考虑输出结果的顺序。

思路

set

新建两个 set 集合，遍历其中一个，判断每个元素在另外一个集合里是否有，有则加入结果数组

双指针

对两个有序数组进行求交集，可以先对原数组排序，然后使用双指针分别指向两个数组的头部，执行以下逻辑：

  1. 如果两个数相等，加入结果数组，然后再跳过和当前数相同的所有数
  2. 如果 p 指向的 nums1 中的元素小于 q 指向的 nums2 中的元素，说明当前 p 指向的元素不存在，令 p++，判断下一个元素
  3. 如果 q 指向的 nums2 中的元素小于 p 指向的 nums1 中的元素，说明当前 q 指向的元素不存在，令 q++，判断下一个元素
  4. 当 p 或 q 遍历完其中一个数组时，循环结束，返回结果数组

解答

set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  const set1 = new Set(nums1);
  const set2 = new Set(nums2);
  const res = [];
  for (const num of set1) {
    if (set2.has(num)) res.push(num);
  }
  return res;
};

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  const res = [];
  nums1.sort((a, b) => Number(a) - Number(b));
  nums2.sort((a, b) => Number(a) - Number(b));
  let p = 0,
    q = 0;
  while (p < nums1.length && q < nums2.length) {
    if (nums1[p] === nums2[q]) {
      res.push(nums1[p]);
      while (p < nums1.length - 1 && nums1[p + 1] === nums1[p]) p++;
      while (q < nums2.length - 1 && nums2[q + 1] === nums2[q]) q++;
      p++;
      q++;
    } else if (nums1[p] < nums2[q]) {
      p++;
    } else {
      q++;
    }
  }
  return res;
};