本文详解如何通过将数组替换为 set 数据结构，将时间复杂度从 o(n²) 优化至 o(n)，大幅提升如 leetcode「存在重复元素」类问题的执行效率。
本文详解如何通过将数组替换为 set 数据结构，将时间复杂度从 o(n²) 优化至 o(n)，大幅提升如 leetcode「存在重复元素」类问题的执行效率。
在 JavaScript 中，算法性能瓶颈往往不在于逻辑本身，而在于数据结构的选择。以 LeetCode 第 217 题「存在重复元素」（Contains Duplicate）为例：给定整数数组 nums，判断是否存在重复元素。一个直观但低效的解法是使用普通数组记录已见元素，并依赖 Array.prototype.includes() 进行查找：
let dupes = [];
for (let i = 0; i < nums.length; i++) {
if (!dupes.includes(nums[i])) {
dupes.push(nums[i]);
}
}
return !(dupes.length === nums.length);该实现看似简洁，实则隐藏严重性能缺陷：includes() 在数组中线性扫描，单次查找时间复杂度为 O(n)；外层循环执行 n 次，整体时间复杂度高达 O(n²)。当输入规模达 10⁵ 量级时，运行时间极易突破数千毫秒（如原题中 6205ms），远落后于前 69% 的提交者（86ms 左右）。
根本优化路径在于用空间换时间，并选用更适合“成员检测”场景的数据结构——Set。Set 是基于哈希表（或等效高效查找结构）实现的集合，其 .has()、.add() 和 .size 均为 平均 O(1) 操作。重构后代码如下：
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return true; // 提前终止，无需遍历全部
}
seen.add(num);
}
return false;✅ 关键优化点说明：
立即学习“Java免费学习笔记（深入）”；
- Set.has() 替代 Array.includes()：查找从 O(n) → O(1)；
- Set.add() 替代 Array.push()：插入保持 O(1)，且自动去重；
- Set.size 替代 Array.length：语义更准确，访问 O(1)；
- 提前返回（Early Exit）：一旦发现重复即刻 return true，避免冗余遍历，最坏情况仍为 O(n)，但平均表现大幅优于原方案。
⚠️ 注意事项：
- 不要误用 Set 后仍做无谓比较（如 !(seen.size === nums.length)），这会强制遍历完整数组，丧失提前终止优势；
- Set 对 NaN 和 -0 等特殊值有精确语义支持（new Set([NaN, NaN]) 大小为 1），优于部分手动哈希方案；
- 若需兼容极老环境（< ES6），可用 Object.create(null) 模拟哈希表，但需手动处理类型转换（如 seen[num] = true），并注意 num 为字符串/布尔等类型时的隐式转换风险。
总结而言，JavaScript 运行时优化的核心原则之一是：匹配操作语义选择最优内置数据结构。面对高频“存在性查询”，Set 或 Map 几乎总是比 Array 更优；理解底层时间复杂度差异，并结合早期退出策略，是写出高性能前端算法代码的关键能力。
