两数之和
题目 给定一个数组 nums 和一个目标值 target，在该数组中找出和为目标值的两个数
输入 nums: [8, 2, 6, 5, 4, 1, 3]， target:7
思路一：暴力解法
最直接的方法是使用两层循环，枚举所有可能的数字对，检查它们的和是否等于目标值。
时间复杂度：O(n²) - 需要两层循环
空间复杂度：O(1) - 只需要常数级别的额外空间
function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [-1, -1]; // 如果没有找到满足条件的数字对
}
const nums = [8, 2, 6, 5, 4, 1, 3];
const target = 7;
console.log(twoSum(nums, target)); // 输出: [1, 5] (2+5=7)思路二：哈希表法
更高效的方法是使用哈希表。只需要遍历一次数组，对于每个元素x，查找哈希表中是否存在target-x。如果存在就找到了答案；如果不存在，将x加入哈希表。
时间复杂度：O(n) - 只需要遍历一次数组 空间复杂度：O(n) - 最坏情况下需要存储所有元素
function twoSum(nums, target) {
const map = new Map(); // 创建一个哈希表
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i]; // 计算互补数
if (map.has(complement)) {
return [map.get(complement), i]; // 找到答案，返回索引
}
map.set(nums[i], i); // 将当前元素加入哈希表
}
return [-1, -1]; // 如果没有找到满足条件的数字对
}
const nums = [8, 2, 6, 5, 4, 1, 3];
const target = 7;
console.log(twoSum(nums, target)); // 输出: [1, 5] (2+5=7)
执行过程解析
以输入 nums = [8, 2, 6, 5, 4, 1, 3], target = 7 为例，哈希表法的执行过程如下：
初始化空哈希表 map = {}
处理 nums[0] = 8:
计算 complement = 7 - 8 = -1
map 中不存在 -1
将 8 加入 map: map = {8: 0}
处理 nums[1] = 2:
计算 complement = 7 - 2 = 5
map 中不存在 5
将 2 加入 map: map = {8: 0, 2: 1}
处理 nums[2] = 6:
计算 complement = 7 - 6 = 1
map 中不存在 1
将 6 加入 map: map = {8: 0, 2: 1, 6: 2}
处理 nums[3] = 5:
计算 complement = 7 - 5 = 2
map 中存在 2，其索引为 1
返回 [1, 3]，表示 nums[1] 和 nums[3] 的和等于 target
因此，结果是 [1, 5]，对应的值是 2 和 5，它们的和是 7。