如何优化求两数组交集函数的O(n²)时间复杂度？

嘿，这个问题太典型了——两层嵌套循环在数据量小的时候没问题，但一旦数组规模上去（比如上千条数据），O(n²)的时间复杂度会让性能直线下降。我给你几个靠谱的优化方案，直接把时间复杂度降到线性级别：

1. 使用Set实现O(1)快速查找（最推荐的方案） #

JavaScript的Set结构天生就是为快速查找设计的，它的has()方法时间复杂度是O(1)。我们可以先把dynamicConfig转换成Set，然后只需要遍历一次staticConfig就能完成匹配，整体时间复杂度降到O(n + m)（n是dynamicConfig的长度，m是staticConfig的长度）。

优化后的代码示例：

var dynamicConfig = ["Test1","Test22","Test3","Test14"];
var staticConfig = [{label: 'Test 1',value: 'Test1'}, {label: 'Test 2',value: 'Test2'}, {label: 'Test 3',value: 'Test3'} ];

function configObj(dynamicConfig, staticConfig) {
  // 把动态配置转成Set，方便快速查找
  const dynamicSet = new Set(dynamicConfig);
  // 遍历静态配置，筛选出value在Set中的项
  return staticConfig.filter(item => dynamicSet.has(item.value));
}

// 测试一下
console.log(configObj(dynamicConfig, staticConfig));
// 输出: [{label: 'Test 1',value: 'Test1'}, {label: 'Test 3',value: 'Test3'}]

2. 用普通对象做映射（兼容旧环境） #

如果需要兼容不支持Set的老浏览器（比如IE11及更早），可以用普通对象来模拟Set的功能：把dynamicConfig的元素作为对象的键，值设为true，然后通过obj.hasOwnProperty()来判断是否存在，同样是O(1)的查找效率。

代码示例：

function configObj(dynamicConfig, staticConfig) {
  const dynamicMap = {};
  // 先把动态配置存入对象
  dynamicConfig.forEach(item => {
    dynamicMap[item] = true;
  });
  // 筛选匹配项
  return staticConfig.filter(item => dynamicMap.hasOwnProperty(item.value));
}

3. 排序+二分查找（适合超大规模数据） #

如果你的数组规模特别大（比如十万级以上），可以先对dynamicConfig进行排序，然后在遍历staticConfig时用二分查找来判断是否存在。这种方案的时间复杂度是O(n log n + m log n)，虽然比前两种稍高，但在极端大数组场景下也能显著优于O(n²)。

不过这种方案需要额外的排序步骤，代码也相对繁琐，所以一般优先用前两种方法。

简单总结一下：前两种方法都是通过“空间换时间”的思路，用额外的O(n)空间来把查找复杂度从O(n)降到O(1)，从而彻底解决两层循环的性能问题。实际开发中，Set方案是最简洁高效的，推荐优先使用。

内容的提问来源于stack exchange，提问作者zm10