1. 两数之和

Origin: LeetCode 1

题目描述

给定一个整数数组 nums 和一个整数目标值 target，在数组中找出和为目标值的两个整数，返回它们的下标。每种输入只对应一个答案，不能使用两次相同元素。

示例

Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0] + nums[1] = 2 + 7 = 9

约束

• 2 <= nums.length <= 10
• -10^9 <= nums[i] <= 10
• -10^9 <= target <= 10

关键信息

• 返回下标，不是值
• 不能用同一元素两次
• 恰好有一个答案

Resolution

我的解法

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

解题思路

哈希表一次遍历。对每个元素 nums[i]，检查 target - nums[i] 是否已在 Map 中：

• 有 → 返回 [map.get(target - cur), i]
• 没有 → 把当前元素存入 Map（值 → 下标）

关键：先检查再存入，避免使用同一元素两次。

踩坑

• 原版先存再查，需要额外判断 map.get(target - cur) !== i 防止用同一元素
• 改成先查再存就不需要这个判断了

复杂度

• 时间：O(n)
• 空间：O(n)