1. 两数之和

题目链接：https://leetcode.cn/problems/two-sum/

代码

function twoSum(nums: number[], target: number): number[] {
    const map = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        const left = target - nums[i];
        if(map.has(left)) return [i, map.get(left)]
        map.set(nums[i], i);
    }
};

思路

使用哈希表在一次遍历中完成查找：

1. 定义 map，记录“数字 -> 下标”的映射
2. 遍历数组中的每个元素 nums[i]
3. 计算还需要的另一个数 left = target - nums[i]
4. 如果 map 中已经存在 left，说明之前出现过能与当前数字凑成目标值的元素，直接返回这两个下标
5. 如果不存在，再把当前数字和下标存入 map

关键点

• 先查找再存入，可以避免同一个元素被重复使用

• map 的键是数字，值是对应下标

• 每次都能在 $O(1)$ 时间内判断补数是否已经出现过

• 时间复杂度 $O(n)$，其中 $n$ 是数组长度

• 空间复杂度 $O(n)$，最坏情况下需要存储所有元素