两数之和 - Stellar Observer Protocol

724 字

4 分钟

两数之和

2025-08-12

Algorithms

数组

/

哈希表

题目描述#

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

解题思路#

哈希映射法：
- 创建哈希表存储元素值到索引的映射
- 遍历数组，计算当前元素与目标的差值
- 在哈希表中查找差值，若存在则返回两数索引
- 否则将当前元素存入哈希表
一次遍历完成：
- 边遍历边检查边存储
- 避免双重循环
顺序无关性：
- 结果索引顺序不影响正确性
- 哈希表记录首次出现位置

关键洞察#

补数定位原理：
- 若 a + b = target，则 b = target - a
- 哈希表记录已遍历元素，快速定位补数
先查后存机制：
- 检查补数后再存入当前元素
- 避免同元素重复使用（如 target=4, a=2）
时空效率最优：
- 牺牲空间换取时间优化
- 一次遍历解决查找问题
边界安全性：
- 题目保证唯一解，无需额外检查
- 空数组或单元素自动返回空

复杂度分析#

指标	说明
时间复杂度	O(n)：单次遍历数组，哈希操作 O(1)
空间复杂度	O(n)：哈希表存储元素索引，最多 n 个条目

代码实现#

1
/**
2
 * @param {number[]} nums
3
 * @param {number} target
4
 * @return {number[]}
5
 */
6
var twoSum = function (nums, target) {
7
    const hashMap = {};
8
    for (let i = 0, len = nums.length; i < len; i++) {
9
        const targetNum = target - nums[i];
10
        if (targetNum in hashMap) {
11
            return [hashMap[targetNum], i]
12
        }
13
        hashMap[nums[i]] = i;
14
    }
15
};