两个数组的交集

问题

给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素必须是唯一的，顺序不限。

示例：

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

解答

方法一：使用 Set

function intersection(nums1, nums2) {
  // 将第一个数组转为 Set，去重并提供 O(1) 查找
  const set1 = new Set(nums1);
  // 用于存储交集结果
  const result = new Set();
  
  // 遍历第二个数组，检查元素是否在 set1 中
  for (const num of nums2) {
    if (set1.has(num)) {
      result.add(num);
    }
  }
  
  return [...result];
}

// 测试
console.log(intersection([1, 2, 2, 1], [2, 2])); // [2]
console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [4, 9]

方法二：使用 filter + Set（简洁写法）

function intersection(nums1, nums2) {
  const set2 = new Set(nums2);
  // 过滤出在 set2 中存在的元素，再去重
  return [...new Set(nums1.filter(num => set2.has(num)))];
}

// 测试
console.log(intersection([1, 2, 2, 1], [2, 2])); // [2]

方法三：排序 + 双指针

function intersection(nums1, nums2) {
  // 先排序
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  
  const result = [];
  let i = 0, j = 0;
  
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] === nums2[j]) {
      // 避免重复添加
      if (result.length === 0 || result[result.length - 1] !== nums1[i]) {
        result.push(nums1[i]);
      }
      i++;
      j++;
    } else if (nums1[i] < nums2[j]) {
      i++;
    } else {
      j++;
    }
  }
  
  return result;
}

// 测试
console.log(intersection([1, 2, 2, 1], [2, 2])); // [2]

扩展：保留重复元素的交集

如果要求交集中保留重复元素（出现次数取较小值）：

function intersect(nums1, nums2) {
  // 用 Map 统计 nums1 中每个元素的出现次数
  const map = new Map();
  for (const num of nums1) {
    map.set(num, (map.get(num) || 0) + 1);
  }
  
  const result = [];
  for (const num of nums2) {
    if (map.get(num) > 0) {
      result.push(num);
      map.set(num, map.get(num) - 1);
    }
  }
  
  return result;
}

// 测试
console.log(intersect([1, 2, 2, 1], [2, 2])); // [2, 2]
console.log(intersect([4, 9, 5], [9, 4, 9, 8, 4])); // [4, 9]

关键点

• Set 提供 O(1) 的查找效率，是处理去重和交集的首选
• 双指针法需要先排序，适合数组已排序或空间受限的场景
• 时间复杂度：Set 方法 O(m+n)，双指针 O(mlogm + nlogn)
• 注意区分”去重交集”和”保留重复的交集”两种变体
• Map 用于统计频次，处理需要保留重复元素的情况