核心内容摘要
蓝莓隐藏路线9.1.1解锁超乎想象的无限可能!_2
作为 LeetCode 第一题两数之和是算法入门的必练经典题也是前端面试中高频考察的基础题。
这道题看似简单却能很好地考察对数组操作、时间 / 空间复杂度优化和哈希表核心思想的理解同时能区分新手和有工程思维的开发者 —— 从暴力枚举到哈希表优化正是「基础实现」到「最优解」的典型思路。
本文将用 JavaScript 实现两种解法从思路分析、代码实现、复杂度拆解、细节深挖四个维度逐一讲解同时补充面试高频考点、新手避坑指南、拓展场景帮你彻底吃透这道题的核心逻辑做到举一反三。
题目要求给定一个整数数组 nums 和一个整数目标值 target请在该数组中找出和为目标值的那两个整数并返回它们的数组下标。
约束条件每种输入只会对应一个有效答案不能使用两次相同的元素可以按任意顺序返回答案。
测试示例
解法一暴力枚举法新手入门必学暴力枚举是最直观的解法核心是通过双层循环模拟「逐个匹配」的过程适合算法新手理解题目的核心要求也是后续优化的基础。
核心思路遍历数组中的每一个元素 nums[i]将其作为第一个数然后从该元素的下一个位置开始遍历剩余元素 nums[j]j i将其作为第二个数判断两者之和是否等于 target。
由于题目保证有且仅有一个有效答案因此一旦找到符合条件的 i 和 j可直接返回结果无需继续遍历。
/** * param {number[]} nums 整数数组 * param {number} target 目标和 * return {number[]} 两个数的数组下标 */functiontwoSum(nums,target){// 外层循环确定第一个数的下标和值for(leti0;inums.length;i){// 内层循环从i1开始避免重复使用元素和重复判断for(letji1;jnums.length;j){// 找到和为target的两个数直接返回下标if(nums[i]nums[j]target){return[i,j];}}}return[];// 题目保证有解理论上不会执行到此处}// 测试示例console.log(twoSum([2,7,11,15],
);// [0,1]console.log(twoSum([3,2,4],
);// [1,2]console.log(twoSum([3,3],
);// [0,1]
关键细节深挖很多新手会疑惑「为什么内层循环要从 i1 开始而不是从 0 开始」这是暴力法的核心细节也是避免踩坑的关键避免重复使用同一个元素如果 j 从 0 开始会出现 ij 的情况此时相当于把同一个元素用了两次违反题目要求减少无效循环提升效率如果 j 从 0 开始会重复判断「i0,j1」和「i1,j0」这两种相同的组合双层循环的次数会从 n(n-
/2 变成 n²增加不必要的计算。
时间 空间复杂度分析复杂度分析是算法题的必考内容也是区分解法优劣的核心指标需从「时间」和「空间」两个维度分析时间复杂度O(n²)n 为数组长度外层循环遍历数组时间为 O(n)对于每个外层循环的元素内层循环都要遍历剩余的 n-i-1 个元素最坏情况下要遍历 n-1 个元素时间也为 O(n)。
双层循环的时间复杂度为两者相乘即 O(n²)。
空间复杂度O(
常数级仅使用了 i、j 两个循环变量没有开辟额外的存储空间空间复杂度为常数级。
解法优缺点✅ 优点逻辑直观、易理解无额外空间开销适合算法新手入门❌ 缺点时间复杂度较高当数组长度接近题目上限 10⁴ 时双层循环会产生约 10⁸ 次计算执行效率大幅降低无法满足工程上的性能要求。
解法二哈希表法最优解面试推荐暴力法的核心问题是内层循环的查找效率太低O(n)而哈希表的查找和插入操作均为 O(
时间复杂度因此我们可以用「空间换时间」的思想通过哈希表存储已遍历的元素将整体时间复杂度优化到 O(n)这也是这道题的最优解面试中优先使用此解法。
核心思想补数思想两数之和的问题可以转化为补数查找问题对于当前遍历的元素 nums[i]要找到另一个数使得两者和为 target这个数就是 complement target - nums[i]补数。
因此我们只需在已遍历过的元素中查找是否存在这个补数如果存在说明补数和当前元素的和为 target直接返回补数的下标和当前下标 i如果不存在将当前元素的值和下标存入哈希表继续遍历下一个元素。
核心优化点用哈希表存储「元素值元素下标」将补数的查找效率从暴力法的 O(n) 降为 O(
。
实现方式一普通对象实现简洁易用JavaScript 中的普通对象可以天然作为简易哈希表键key 存储数组元素值值value 存储对应下标适合日常开发和快速实现。
完整代码/** * param {number[]} nums 整数数组 * param {number} target 目标和 * return {number[]} 两个数的数组下标 */functiontwoSum(nums,target){constmap{};// 哈希表key 数组元素值value 元素下标// 一次遍历数组时间复杂度O(n)for(leti0;inums.length;i){constcomplementtarget-nums[i];// 计算当前元素的补数// 判断补数是否存在于哈希表中自身属性if(map.hasOwnProperty(complement)){return[map[complement],i];// 存在则返回补数下标和当前下标}// 不存在则将当前元素和下标存入哈希表map[nums[i]]i;}return[];// 题目保证有解理论上不会执行到此处}// 测试示例console.log(twoSum([2,7,11,15],
);// [0,1]console.log(twoSum([3,2,4],
);// [1,2]console.log(twoSum([3,3],
);// [0,1]关键细节深挖为什么用 hasOwnProperty 而不是直接判断 map[complement]这是新手最容易踩的坑举两个典型场景说明当补数的值为 0 时如果 map[0] 0直接判断 if (map[0]) 会得到 false因为 0 在 JavaScript 中是假值会误判补数不存在避免原型链属性干扰JavaScript 对象会继承 Object.prototype 的属性如 toString、hasOwnProperty如果数组中存在这些属性名的数值极端场景会导致判断错误。
hasOwnProperty 方法会仅判断对象的自身属性忽略原型链属性能避免上述两种坑保证判断的准确性。
实现方式二ES6 Map 实现更严谨面试优先ES6 新增的 Map 是专门的哈希表数据结构相比普通对象在键值类型、判断逻辑、遍历方式上更具优势面试中推荐使用能体现开发者的 ES6 基础和工程严谨性。
Map 对比普通对象的核心优势键的类型无限制普通对象的键只能是字符串 / 符号Symbol而 Map 的键可以是任意类型数字、布尔值、对象等判断键存在更直观Map 提供 has() 方法专门判断键是否存在无需像对象一样用 hasOwnProperty 规避坑无原型链干扰Map 不会继承任何原型属性天然避免属性名冲突可直接获取键值对数量Map 提供 size 属性而对象需要手动遍历才能统计键值对数量。
/** * param {number[]} nums 整数数组 * param {number} target 目标和 * return {number[]} 两个数的数组下标 */functiontwoSum(nums,target){constmapnewMap();// 初始化ES6 Map哈希表for(leti0;inums.length;i){constcomplementtarget-nums[i];// 计算补数if(map.has(complement)){// 判断补数是否存在return[map.get(complement),i];// 存在则获取补数下标并返回}map.set(nums[i],i);// 不存在则存入当前元素和下标}return[];// 题目保证有解理论上不会执行到此处}// 测试示例console.log(twoSum([2,7,11,15],
);// [0,1]console.log(twoSum([3,2,4],
);// [1,2]console.log(twoSum([3,3],
);// [0,1]
天然避坑避免重复使用同一个元素哈希表法的遍历逻辑是先判断补数再存入当前元素因此哈希表中存储的始终是已遍历过的元素补数不可能是当前元素本身天然满足「不能使用两次相同元素」的题目要求无需额外判断。
时间 空间复杂度分析时间复杂度O(n)n 为数组长度仅需一次遍历数组每次遍历中的补数查找和哈希表插入操作均为 O(
时间复杂度因此整体时间复杂度为 O(n)相比暴力法效率提升显著完全适配题目中 nums.length 10⁴ 的约束。
空间复杂度O(n)n 为数组长度需要开辟哈希表存储已遍历的元素最坏情况下有效答案在数组最后两个位置需要存储 n-1 个元素因此空间复杂度为 O(n)。
面试高频考点 新手避坑指南这道题虽然简单但面试中面试官会通过追问细节考察你的基础功底和工程思维以下是高频考点和避坑要点务必掌握
高频追问Q1为什么暴力法的内层循环要从 i1 开始A1一是避免重复使用同一个元素二是减少无效循环避免重复判断相同的元素组合提升效率。
Q2为什么哈希表法能避免重复使用同一个元素A2因为哈希表法是先判断补数再存入当前元素哈希表中只有已遍历过的元素补数不可能是当前元素本身。
Q3普通对象和 Map 作为哈希表你更推荐哪种为什么A3推荐 Map因为 Map 键的类型无限制、判断键存在更直观、无原型链属性干扰工程上更严谨也能体现 ES6 基础。
Q4这道题的时间复杂度能优化到低于 O(n) 吗A4不能因为要找到和为 target 的两个数至少需要遍历一次数组因此时间复杂度的下界是 O(n)。