0001.两数之和
难度：🟢 简单
标签：数组、哈希表
链接：1. 两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 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^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9只会存在一个有效答案
解题思路
核心思想
本题的核心思想是，对于数组中的每一个元素 x，我们需要快速判断数组中是否存在另一个元素 y，使得 x + y = target。这个 y 就是 target - x，我们称之为 x 的“补数”。问题就转化为：如何高效地查找每个元素的“补数”。
思路选择
最直观的方法是暴力枚举：用两层循环，对数组中每一对不同的元素进行求和判断，时间复杂度为 O(n²)，效率较低。
为了优化查找过程，我们可以采用 “空间换时间” 的策略，使用 哈希表（在 JavaScript 中是 Map 对象）。哈希表提供了近乎 O(1) 的查找效率。我们只需遍历一次数组，在遍历每个元素时，查找其“补数”是否已存在于哈希表中。
关键步骤
初始化：创建一个空的哈希表
map，用于存储已经遍历过的数字及其对应的索引，格式为{ 数字: 索引 }。遍历数组：用一个循环从头到尾遍历
nums数组，设当前元素为nums[i]。计算补数：计算当前元素所需的“补数”
complement = target - nums[i]。查找补数：在哈希表
map中查找是否存在键为complement的项。判断结果：
如果 存在，说明
complement这个数字之前已经出现过。我们立即找到了答案，返回[map中补数的索引, 当前索引 i]。如果 不存在，说明还没找到配对。将 当前数字
nums[i]和它的索引i存入哈希表，以便后续的数字能和它进行配对。
返回：由于题目保证有且只有一个解，循环一定会找到答案并返回。
代码实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
// 创建一个 Map 实例，用于存储数字及其索引
let map = new Map();
for (let i = 0; i < nums.length; i++) {
// 计算需要的另一个数字（补数）
let complement = target - nums[i];
// 检查 Map 中是否存在所需的补数
if (map.has(complement)) {
// 如果存在，直接返回两个数的索引
return [map.get(complement), i];
}
// 如果不存在，将当前数字和它的索引存入 Map，供后续查找
map.set(nums[i], i);
}
};
复杂度分析
时间复杂度：O(n) 我们只需要遍历一次数组。对于每个元素，在哈希表中的插入和查找操作的平均时间复杂度都是 O(1)，因此总时间复杂度与数组长度 n 成正比。
空间复杂度：O(n) 我们使用了一个哈希表来存储数字。在最坏的情况下，我们需要将所有 n 个元素都存入哈希表中，所以所需的额外空间与数组长度 n 成正比。
相关题目
总结
本题是 LeetCode 的开篇之作，也是哈希表应用的经典范例。它完美地展示了如何利用数据结构的特性来优化算法。通过牺牲一定的空间（O(n)），我们将时间复杂度从暴力的 O(n²) 降低到了线性的 O(n)，这是算法设计中非常重要的“空间换时间”思想。