两数之和
🟢 简单题目描述
给定一个整数数组 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^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- 只存在一个有效答案
解法一
参考答案 (2 个标签)
暴力枚举 O(n²)
思路
使用两层循环，外层循环遍历每个元素，内层循环查找是否存在另一个元素使得两数之和等于目标值。
代码实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
function twoSum(nums, target) {
const n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}复杂度分析
- 时间复杂度：O(n²)，其中 n 是数组长度。最坏情况下需要遍历所有数对。
- 空间复杂度：O(1)，只使用常数级别的额外空间。
解法二
参考答案 (2 个标签)
哈希表 O(n)
思路
利用哈希表存储已经遍历过的元素及其下标。对于每个元素 nums[i]，检查 target - nums[i] 是否在哈希表中，如果存在则找到了答案。
代码实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
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 [];
}复杂度分析
- 时间复杂度：O(n)，只需要遍历一次数组。
- 空间复杂度：O(n)，哈希表最多存储 n 个元素。
为什么先检查再插入？
注意代码中先检查 complement 是否存在，再插入当前元素。这样可以避免同一个元素被使用两次的情况。例如 nums = [3, 3], target = 6，如果先插入再检查，第一个 3 插入后，检查时发现 complement = 3 存在，但那是自己，会得到错误答案。