LeetCode 1：两数之和（Two Sum）

给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。你可以按任意顺序返回答案。示例示例 1 输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 示例 2 输入nums [3,2,4], target 6 输出[1,2] 示例 3 输入nums [3,3], target 6 输出[0,1]约束条件2 nums.length 10⁴-10⁹ nums[i] 10⁹-10⁹ target 10⁹只会存在一个有效答案二、题目解析核心问题拆解关键点分析输入整数数组 目标值输出两个数的下标不是数值本身约束同一元素不能使用两次保证有且仅有一个解思考方向原问题nums[i] nums[j] target转化思维对于每个 nums[i]寻找 target - nums[i]如何快速查找?哈希表 O(1)三、算法解答算法一暴力枚举法1. 算法原理描述核心思想穷举所有可能的两数组合检查它们的和是否等于目标值。实现方式使用两层循环外层循环固定第一个数nums[i]内层循环遍历其后的所有数nums[j]j i检查nums[i] nums[j] target2. 算法解答过程以nums [2, 7, 11, 15],target 9为例外层 i内层 jnums[i]nums[j]和是否等于 target01279✅ 找到返回[0, 1]3. 算法原理图像解析复杂度分析⏱ 时间: O(n²) 空间: O(1)暴力枚举流程✅ 是❌ 否开始外层循环 i 0内层循环 j 1nums[0] nums[1] 2 7 9 target?返回 [0, 1]j, 继续内层若内层结束i, 继续外层数组 nums, target 9[0]2[1]7[2]11[3]154. 算法代码class Solution { public: vectorint twoSum(vectorint nums, int target) { int n nums.size(); // 外层循环固定第一个数 for (int i 0; i n - 1; i) { // 内层循环遍历第一个数之后的所有数 for (int j i 1; j n; j) { // 检查两数之和是否等于目标值 if (nums[i] nums[j] target) { return {i, j}; } } } // 题目保证有解这里不会执行到 return {}; } };5. 复杂度分析复杂度类型值说明时间复杂度O(n²)两层嵌套循环最坏情况遍历 n(n-1)/2 次空间复杂度O(1)只使用常数额外空间6. 使用范围场景适用性数据规模小n 1000✅ 适用数据规模大❌ 会超时对空间要求极高✅ 适用面试中作为初始解法✅ 适用但需优化算法二哈希表法一遍哈希⭐ 最优解1. 算法原理描述核心思想将「寻找两数之和」转化为「寻找差值」问题。关键转换nums[i] nums[j] target ↓ 转化 nums[j] target - nums[i]实现方式使用哈希表存储已遍历过的元素及其下标对于当前元素nums[i]计算complement target - nums[i]在哈希表中查找complement是否存在若存在说明找到答案若不存在将当前元素加入哈希表优势哈希表的查找时间复杂度为 O(1)整体只需一次遍历。2. 算法解答过程以nums [2, 7, 11, 15],target 9为例步骤当前元素complement哈希表查找操作哈希表状态1nums[0]29-277 不存在存入2nums[1]79-722 存在下标0返回 [0,1]-3. 算法原理图像解析 核心要点边遍历边建表先查找再存入O(1) 查找步骤2: 处理 nums[1] 7计算 complement 9 - 7 2哈希表中查找 2✅ 找到! 下标0返回 [0, 1]步骤1: 处理 nums[0] 2计算 complement 9 - 2 7哈希表中查找 7❌ 未找到存入哈希表{2: 0}输入: nums [2,7,11,15], target 9271115哈希表状态变化存入 2:0查找2处理7时2 → 0查找2 ✅处理2后2 → 0初始状态空 ∅4. 算法代码class Solution { public: vectorint twoSum(vectorint nums, int target) { // 哈希表key 数值value 下标 unordered_mapint, int hashMap; for (int i 0; i nums.size(); i) { // 计算当前元素的配对值 int complement target - nums[i]; // 在哈希表中查找配对值 if (hashMap.find(complement) ! hashMap.end()) { // 找到了返回两个下标 return {hashMap[complement], i}; } // 未找到将当前元素存入哈希表 hashMap[nums[i]] i; } // 题目保证有解这里不会执行到 return {}; } };5. 代码详解// 关键点解析 // 1. 为什么用 unordered_map 而不是 map // - unordered_map 基于哈希表查找/插入 O(1) // - map 基于红黑树查找/插入 O(log n) // 2. 为什么先查找再存入 // - 避免同一元素被使用两次 // - 例如nums [3, 3], target 6 // - 第一个3存入后第二个3能找到第一个3 // 3. hashMap.find() vs hashMap.count() // - find() 返回迭代器未找到返回 end() // - count() 返回 0 或 1 // - 两种写法都可以find() 更常用6. 复杂度分析复杂度类型值说明时间复杂度O(n)只需遍历数组一次哈希表操作 O(1)空间复杂度O(n)最坏情况需存储 n-1 个元素7. 使用范围