如何将TypeScript嵌套for循环从O(n²)优化至O(n)或相近复杂度

优化思路 #

原双重循环实现的时间复杂度为O(n²)，优化核心是先将arr2的id存入查询效率为O(1)的哈希结构，再遍历arr1完成checked属性赋值，整体时间复杂度可降至O(n)，以下是具体实现方案：

方案1：使用Set存储id（仅需判断id是否存在时推荐，最简洁） #

// 预提取arr2所有id存入Set，时间复杂度O(n)
const arr2IdSet = new Set(arr2.map(item => item.id))
// 遍历arr1批量赋值checked属性，时间复杂度O(n)
for (const item of arr1) {
  item.checked = arr2IdSet.has(item.id)
}

优势：代码简洁无冗余，Set的has方法平均时间复杂度为O(1)，无额外逻辑开销

方案2：使用Map存储id与元素映射（需要关联获取arr2对应元素时推荐） #

如果后续逻辑需要用到arr2中匹配id的其他属性，可以用Map同时存储id和对应的完整元素：

// 预构建arr2的id-元素映射，时间复杂度O(n)
const arr2Map = new Map(arr2.map(item => [item.id, item]))
for (const item of arr1) {
  item.checked = arr2Map.has(item.id)
  // 若需要可直接获取arr2的匹配元素：const matchedItem = arr2Map.get(item.id)
}

方案3：使用普通对象做哈希表（兼容极低版本JS运行环境时推荐） #

如果运行环境不支持ES6的Set/Map，可使用普通对象实现相同效果，时间复杂度同样为O(n)：

const arr2IdMap = {}
// 预存arr2所有id到对象中
arr2.forEach(item => {
  arr2IdMap[item.id] = true
})
for (const item of arr1) {
  item.checked = !!arr2IdMap[item.id]
}

注意：该方案仅适用于id为字符串/数字类型的场景，若id为引用类型需使用Map实现

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