两个数组的交集

问题

给定两个数组，返回它们的交集。如 [1, 2, 2, 1] 和 [2, 2] 的交集是 [2] 或 [2, 2]（取决于是否保留重复）。

这是 LeetCode 经典题目：

• 349. 两个数组的交集 - 结果去重
• 350. 两个数组的交集 II - 保留重复

答案

根据是否需要去重，有不同的解法。核心思想是使用 Set 或 Map 进行快速查找。

---

去重交集（LeetCode 349）

Set 解法

function intersection(nums1: number[], nums2: number[]): number[] {
  const set1 = new Set(nums1);
  const set2 = new Set(nums2);

  const result: number[] = [];

  for (const num of set1) {
    if (set2.has(num)) {
      result.push(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]

一行代码

const intersection = (nums1: number[], nums2: number[]): number[] =>
  [...new Set(nums1)].filter((n) => new Set(nums2).has(n));

优化版本（遍历较小的 Set）

function intersectionOptimized(nums1: number[], nums2: number[]): number[] {
  const set1 = new Set(nums1);
  const set2 = new Set(nums2);

  // 遍历较小的 Set
  const [smaller, larger] = set1.size < set2.size 
    ? [set1, set2] 
    : [set2, set1];

  return [...smaller].filter((num) => larger.has(num));
}

---

保留重复交集（LeetCode 350）

Map 计数解法

function intersect(nums1: number[], nums2: number[]): number[] {
  // 统计 nums1 中每个数字的出现次数
  const countMap = new Map<number, number>();

  for (const num of nums1) {
    countMap.set(num, (countMap.get(num) || 0) + 1);
  }

  const result: number[] = [];

  // 遍历 nums2，在 countMap 中查找
  for (const num of nums2) {
    const count = countMap.get(num);
    if (count && count > 0) {
      result.push(num);
      countMap.set(num, count - 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]

排序 + 双指针

function intersectSorted(nums1: number[], nums2: number[]): number[] {
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);

  const result: number[] = [];
  let i = 0;
  let j = 0;

  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] === nums2[j]) {
      result.push(nums1[i]);
      i++;
      j++;
    } else if (nums1[i] < nums2[j]) {
      i++;
    } else {
      j++;
    }
  }

  return result;
}

何时用双指针

• 数组已排序或排序代价可接受
• 内存受限，无法使用额外哈希表
• 数据量大，需要流式处理

---

通用交集函数

interface IntersectionOptions {
  unique?: boolean;        // 是否去重
  comparator?: <T>(a: T, b: T) => boolean; // 自定义比较函数
}

function arrayIntersection<T>(
  arr1: T[],
  arr2: T[],
  options: IntersectionOptions = {}
): T[] {
  const { unique = true, comparator } = options;

  if (comparator) {
    // 使用自定义比较器（O(n*m)）
    const result: T[] = [];
    const used = new Set<number>();

    for (const item1 of arr1) {
      for (let j = 0; j < arr2.length; j++) {
        if (!used.has(j) && comparator(item1, arr2[j])) {
          result.push(item1);
          if (!unique) used.add(j);
          break;
        }
      }
    }

    return unique ? [...new Set(result)] : result;
  }

  // 使用 Map（O(n+m)）
  if (unique) {
    const set2 = new Set(arr2);
    return [...new Set(arr1)].filter((item) => set2.has(item));
  }

  const countMap = new Map<T, number>();
  for (const item of arr1) {
    countMap.set(item, (countMap.get(item) || 0) + 1);
  }

  const result: T[] = [];
  for (const item of arr2) {
    const count = countMap.get(item);
    if (count && count > 0) {
      result.push(item);
      countMap.set(item, count - 1);
    }
  }

  return result;
}

// 测试
console.log(arrayIntersection([1, 2, 2, 1], [2, 2])); // [2]
console.log(arrayIntersection([1, 2, 2, 1], [2, 2], { unique: false })); // [2, 2]

---

对象数组交集

interface User {
  id: number;
  name: string;
}

function intersectByKey<T, K extends keyof T>(
  arr1: T[],
  arr2: T[],
  key: K
): T[] {
  const keySet = new Set(arr2.map((item) => item[key]));
  return arr1.filter((item) => keySet.has(item[key]));
}

// 测试
const users1: User[] = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' },
  { id: 3, name: 'Charlie' }
];

const users2: User[] = [
  { id: 2, name: 'Bob' },
  { id: 4, name: 'David' }
];

console.log(intersectByKey(users1, users2, 'id'));
// [{ id: 2, name: 'Bob' }]

使用自定义比较器

function intersectWith<T>(
  arr1: T[],
  arr2: T[],
  isEqual: (a: T, b: T) => boolean
): T[] {
  return arr1.filter((item1) => arr2.some((item2) => isEqual(item1, item2)));
}

// 测试
const result = intersectWith(
  [{ x: 1, y: 2 }, { x: 3, y: 4 }],
  [{ x: 1, y: 2 }, { x: 5, y: 6 }],
  (a, b) => a.x === b.x && a.y === b.y
);
// [{ x: 1, y: 2 }]

---

多个数组的交集

function intersectionMultiple<T>(...arrays: T[][]): T[] {
  if (arrays.length === 0) return [];
  if (arrays.length === 1) return [...new Set(arrays[0])];

  // 从最短数组开始
  const sorted = [...arrays].sort((a, b) => a.length - b.length);
  const [first, ...rest] = sorted;

  // 用 Set 存储第一个数组的元素
  let result = new Set(first);

  // 依次与其他数组取交集
  for (const arr of rest) {
    const current = new Set(arr);
    result = new Set([...result].filter((item) => current.has(item)));

    // 提前结束
    if (result.size === 0) break;
  }

  return [...result];
}

// 测试
console.log(intersectionMultiple([1, 2, 3], [2, 3, 4], [3, 4, 5])); // [3]
console.log(intersectionMultiple([1, 2], [2, 3], [3, 4])); // []

保留重复的多数组交集

function intersectMultiple<T>(...arrays: T[][]): T[] {
  if (arrays.length === 0) return [];
  if (arrays.length === 1) return [...arrays[0]];

  // 统计每个数组中元素的出现次数
  const countMaps = arrays.map((arr) => {
    const map = new Map<T, number>();
    for (const item of arr) {
      map.set(item, (map.get(item) || 0) + 1);
    }
    return map;
  });

  const result: T[] = [];
  const firstMap = countMaps[0];

  // 遍历第一个数组的元素
  for (const [item, count] of firstMap) {
    // 取所有数组中该元素出现次数的最小值
    let minCount = count;

    for (let i = 1; i < countMaps.length; i++) {
      const c = countMaps[i].get(item) || 0;
      minCount = Math.min(minCount, c);
      if (minCount === 0) break;
    }

    // 添加 minCount 个该元素
    for (let j = 0; j < minCount; j++) {
      result.push(item);
    }
  }

  return result;
}

// 测试
console.log(intersectMultiple([1, 2, 2, 3], [2, 2, 3, 4], [2, 3, 3, 5]));
// [2, 3]

---

大数据量优化

流式处理（适用于文件或数据库）

async function* intersectStreams<T>(
  stream1: AsyncIterable<T>,
  stream2: AsyncIterable<T>
): AsyncGenerator<T> {
  // 将第一个流加载到 Set
  const set1 = new Set<T>();
  for await (const item of stream1) {
    set1.add(item);
  }

  // 流式检查第二个流
  const seen = new Set<T>();
  for await (const item of stream2) {
    if (set1.has(item) && !seen.has(item)) {
      seen.add(item);
      yield item;
    }
  }
}

分批处理

function intersectInBatches<T>(
  arr1: T[],
  arr2: T[],
  batchSize: number = 10000
): T[] {
  const set1 = new Set(arr1);
  const result: T[] = [];

  for (let i = 0; i < arr2.length; i += batchSize) {
    const batch = arr2.slice(i, i + batchSize);

    for (const item of batch) {
      if (set1.has(item)) {
        result.push(item);
        set1.delete(item); // 去重
      }
    }
  }

  return result;
}

---

复杂度分析

方法	时间复杂度	空间复杂度	适用场景
Set 解法	$O(n + m)$	$O(\min(n, m))$	去重交集
Map 计数	$O(n + m)$	$O(\min(n, m))$	保留重复
排序+双指针	$O(n \log n + m \log m)$	$O(1)$	内存受限
嵌套循环	$O(n \cdot m)$	$O(1)$	小数据量

---

常见面试问题

Q1: 如果数组已排序，如何优化？

答案：

使用双指针，无需额外空间：

function intersectSortedArrays(nums1: number[], nums2: number[]): number[] {
  const result: number[] = [];
  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;
}

Q2: 如果 nums2 存储在磁盘上，无法全部加载到内存怎么办？

答案：

1. 外部排序：对两个数组分别排序，然后归并
2. 布隆过滤器：用 nums1 构建布隆过滤器，快速过滤 nums2
3. 分块处理：将 nums1 分块加载，多次扫描 nums2

// 使用布隆过滤器的伪代码
class BloomFilter {
  private bits: Uint8Array;
  private hashCount: number;

  constructor(size: number, hashCount: number) {
    this.bits = new Uint8Array(Math.ceil(size / 8));
    this.hashCount = hashCount;
  }

  add(item: number): void {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this.hash(item, i);
      this.bits[Math.floor(index / 8)] |= 1 << (index % 8);
    }
  }

  mightContain(item: number): boolean {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this.hash(item, i);
      if (!(this.bits[Math.floor(index / 8)] & (1 << (index % 8)))) {
        return false;
      }
    }
    return true;
  }

  private hash(item: number, seed: number): number {
    // 简化的哈希函数
    return Math.abs((item * 31 + seed) % (this.bits.length * 8));
  }
}

function intersectWithBloomFilter(
  nums1: number[],
  nums2Stream: Iterable<number>
): number[] {
  // 用 nums1 构建布隆过滤器和精确 Set
  const bloom = new BloomFilter(nums1.length * 10, 3);
  const exactSet = new Set(nums1);

  for (const num of nums1) {
    bloom.add(num);
  }

  // 流式处理 nums2
  const result: number[] = [];
  const seen = new Set<number>();

  for (const num of nums2Stream) {
    // 布隆过滤器快速过滤
    if (bloom.mightContain(num) && exactSet.has(num) && !seen.has(num)) {
      result.push(num);
      seen.add(num);
    }
  }

  return result;
}

Q3: 如何计算两个数组的并集、差集？

答案：

// 并集
function union<T>(arr1: T[], arr2: T[]): T[] {
  return [...new Set([...arr1, ...arr2])];
}

// 差集（arr1 中有但 arr2 中没有的元素）
function difference<T>(arr1: T[], arr2: T[]): T[] {
  const set2 = new Set(arr2);
  return [...new Set(arr1)].filter((item) => !set2.has(item));
}

// 对称差集（只在一个数组中出现的元素）
function symmetricDifference<T>(arr1: T[], arr2: T[]): T[] {
  const set1 = new Set(arr1);
  const set2 = new Set(arr2);

  return [
    ...[...set1].filter((item) => !set2.has(item)),
    ...[...set2].filter((item) => !set1.has(item))
  ];
}

// 测试
console.log(union([1, 2, 3], [2, 3, 4])); // [1, 2, 3, 4]
console.log(difference([1, 2, 3], [2, 3, 4])); // [1]
console.log(symmetricDifference([1, 2, 3], [2, 3, 4])); // [1, 4]

相关链接

• 349. 两个数组的交集 - LeetCode
• 350. 两个数组的交集 II - LeetCode
• Set - MDN
• Map - MDN