# 349.两个数组的交集

# 方法一：两个集合

计算两个数组的交集，最直观的方法就是遍历数组 nums1 对于其中的每个元素，遍历数组 nums2 判断该元素是否存在nums2中，如果存在，则将该元素添加到返回值，假设数组nums1和nums2的长度分别是m和n，则遍历数组nums1需要O(m)的时间，判断 nums1中每个元素是否在nums2中需要O(n)的时间，因此总的时间复杂度是O(mn)。

如果使用集合存储元素，则可以在O(1)的时间内判断一个元素是否在集合中，从而降低时间复杂度。

首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到O(m+n)。

const set_intersection = (set1, set2) => {
  if (set1.size > set2.size) {
    let temp = null
    temp = set1
    set1 = set2
    set2 = temp
  }
  // 新建一个集合
  const intersection = new Set();
  // 遍历set1 是较小的一个集合
  for (const num of set1) {
    // 如果set2中也包含
    if (set2.has(num)) {
      // 就加入结果集
      intersection.add(num);
    }
  }
  // 最后的返回值是一个数组
  return [...intersection];
}

var intersection = function(nums1, nums2) {
  // 将数组转化为set set 天生有去重的能力
  const set1 = new Set(nums1);
  const set2 = new Set(nums2);
  // 调用方法
  return set_intersection(set1, set2);
};

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
27
28

复杂度分析

时间复杂度：O(m+n)，其中m和n分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要O(m+n)的时间，遍历较小的集合并判断元素是否在另一个集合中需要 O(min(m,n))的时间，因此总时间复杂度是 O(m+n)。
空间复杂度：O(m+n), 其中m和n分别是两个数组的长度，空间复杂度主要取决于两个集合。

# 方法二: 排序+双指针

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

首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组一定是递增的，为了保证加入的元素的唯一性，我们需要额外记录变量pre表示上一次加入答案数组的元素。

初始化的时候，两个指针分别指向两个数组的头部，每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于pre，将该数字添加到答案并更新pre变量，同时将两个指针都右移一位，当至少有一个指针超出数组范围的时候，遍历结束。

var intersection = function(nums1, nums2) {
  nums1.sort((x, y) => x - y);
  nums2.sort((x, y) => x - y);
  const length1 = nums1.length, length2 = nums2.length;
  let index1 = 0, index2 = 0;
  const intersection = [];
  while (index1 < length1 && index2 < length2) {
    const num1 = nums1[index1], num2 = nums2[index2];
    if (num1 === num2) {
        // 保证加入元素的唯一性
        if (!intersection.length || num1 !== intersection[intersection.length - 1]) {
            intersection.push(num1);
        }
        index1++;
        index2++;
    } else if (num1 < num2) {
        index1++;
    } else {
        index2++;
    }
  }
  return intersection;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

时间复杂度：O(mlogm + nlogn)，其中 m 和 n 分别是两个数组的长度。对两个数组排序的时间复杂度分别是 O(mlogm) 和 O(nlogn)，双指针寻找交集元素的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+ nlog n)。
空间复杂度：O(logm+logn)，其中 m和 n 分别是两个数组的长度。空间复杂度主要取决于排序使用的额外空间。