LeetCode 1.两数之和 | 从暴力枚举到线性优化

📋 题目基础信息

• 题目序号：LeetCode 1. 两数之和
• 题目难度：Easy（简单）
• 题目地址：https://leetcode.cn/problems/two-sum/
• 题目标签：数组、哈希表

📝 题目描述

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

✅ 题目约束：

• 每种输入只会对应一个有效答案
• 不能重复使用同一个元素
• 可以按任意顺序返回最终结果下标

🚀 题目进阶要求：尝试设计一个时间复杂度优于O(n²)的算法

🖼️ 题目示例：

• 示例1：输入nums = [2,7,11,15], target = 9，输出[0,1]， 解释：nums[0] + nums[1] = 2 + 7 = 9
• 示例2：输入nums = [3,2,4], target = 6，输出[1,2]
• 示例3：输入nums = [3,3], target = 6，输出[0,1]

📌 数据范围提示

• 数组长度：2 <= nums.length <= 10^4
• 数值范围：-10^9 <= nums[i] <= 10^9
• 目标值范围：-10^9 <= target <= 10^9

💡 解题总览

本篇收录三种完整解法，由浅入深，覆盖新手学习、刷题、面试全场景：

1. Java 双层暴力循环：零门槛理解，适合入门算法思维
2. JS 原生 Object 哈希表：通俗“小本本”写法，新手友好，易懂易学
3. JS Map 哈希表（最优解）：规范标准写法，面试、刷题首选，效率最高

🔧 解法一：暴力枚举（双层循环）

1. 🧠 解题思路

暴力解法是新手最容易理解的基础解法，核心思路是枚举所有两数组合，具体步骤如下：

• 第一层循环：固定数组中当前遍历的元素nums[i]
• 第二层循环：从i + 1位置开始遍历后续元素，避免重复使用同一个元素、避免重复比对组合
• 判断两数之和是否等于目标值，匹配成功直接返回双下标[i, j]
• 题目保证唯一解，找到结果即可直接终止遍历

2. 💻 完整代码

publicclassSolution{publicint[]twoSum(int[]nums,inttarget){// 固定第一个数for(inti=0;i<nums.length;i++){// 第二个数从 i+1 开始遍历，避免重复使用同一元素、避免重复组合for(intj=i+1;j<nums.length;j++){// 匹配目标值，直接返回双下标if(nums[i]+nums[j]==target){returnnewint[]{i,j};}}}// 题目保证有唯一解，兜底返回空数组returnnewint[]{};}}

3. ⏱️ 复杂度分析

时间复杂度：O(n²)，双层嵌套循环，数据量较大时会超时

空间复杂度：O(1)，仅使用常数级临时变量，无额外内存开销

4. ✅ 优缺点总结

优点：逻辑直白、零算法门槛、无需额外数据结构，新手极易理解

缺点：时间效率差，无法通过大数据测试用例，仅适合入门学习，面试不推荐

⚡ 解法二：JS 原生 Object 哈希表

1. 🧠 解题思路

暴力解法效率低的核心原因是重复遍历，哈希解法采用空间换时间的经典算法思想，只用一次遍历即可解题，新手友好的“小本本”逻辑如下：

• 定义空对象作为备忘录，记录已遍历数字 : 对应下标
• 通过公式搭档数 = target - 当前数字，反向求解需要匹配的数值
• 优先在备忘录中查找搭档数，存在则直接返回双下标
• 未找到则将当前数字和下标存入备忘录，继续遍历

核心关键：先查找、后存储，从根源避免元素重复使用，符合题目规则。

核心顺序：先查找，后存储，完美避免自己和自己匹配，满足题目不能重复使用同一元素的要求。

2. 💻 完整代码

functiontwoSum(nums,target){constprevNums={};// 👉 准备一个空白小本本，记录走过的数字和下标for(leti=0;i<nums.length;i++){// 👉 逐个走数组里的数字constcurNum=nums[i];// 👉 拿到当前这个数字consttargetNum=target-curNum;// 👉 算：还缺哪个数才能凑目标consttargetNumIndex=prevNums[targetNum];// 👉 翻本本找这个“缺的数”if(targetNumIndex!==undefined){// 👉 本本里找到了缺的数 → 答案出现，返回两个下标return[targetNumIndex,i];}else{// 👉 本本里没找到 → 把当前数字+位置记进本本prevNums[curNum]=i;}}return[];}

3. ⏱️ 复杂度与特点

时间复杂度：O(n)，仅遍历数组一次，效率极高

空间复杂度：O(n)，需要额外空间存储遍历过的数值下标

特点：代码拟人化、通俗易懂，非常适合新手理解哈希表“记录-查找”的核心原理

🏆 解法三：JS Map 哈希表（面试最优版）

1. 🧠 解题思路

整体逻辑和 Object 哈希解法完全一致，同样遵循一次遍历、先查后存的规则，唯一区别是使用 JS 标准Map结构存储数据，优势如下：

• Map 是专业键值对存储结构，无隐式类型转换问题
• API 语义清晰（has/get/set），代码更规范
• 适配所有特殊测试用例，刷题、面试通用

2. 💻 完整代码

consttwoSum=(nums,target)=>{// 新建空 Map，用来记录：数字 → 对应下标constmap=newMap();// 遍历数组每一个元素for(leti=0;i<nums.length;i++){// 计算需要凑数的另一半（搭档数）constdiff=target-nums[i];// 如果 Map 里已经有这个搭档数，说明找到答案if(map.has(diff)){// 返回 [搭档数下标, 当前下标]return[map.get(diff),i];}// 没找到，就把当前数字和下标存进 Mapmap.set(nums[i],i);}return[];};

3. ✨ 特点优势

• 性能稳定，不丢失精度，适配全部 LeetCode 测试用例
• 写法专业规范，是前端面试、算法刷题的首选最优解
• 相比原生 Object 写法，容错率更高，工程性更强

📊 三种解法全面对比

⚠️ 核心易错点总结

刷题过程中极易踩坑的核心要点，务必牢记：

• 遍历顺序不能颠倒：必须先查找、后存储，否则会匹配到自身元素，违反题目规则
• 返回值区分：题目要求返回数组下标，不是数组数值，切忌混淆
• 两种哈希区别：Object 和 Map 逻辑完全一致，仅语法差异，新手学 Object 理解原理，面试写 Map 保证规范
• 复杂度取舍：哈希解法牺牲少量内存，将时间复杂度从 O(n²) 优化至 O(n)，是算法「空间换时间」的经典示范