两数之和

这道题算是 LeetCode 的入门题了，但仔细想想，其实挺有意思的。题目要求很简单：给你一个整数数组和一个目标值，找出数组中两个数的和等于目标值，返回这两个数的下标。

注意几个关键点：返回的是下标而不是值，同一个元素不能使用两次（但值可以相同，比如 [3, 3] 在 target=6 时可以用两个3），题目保证有且仅有一组解。

最直观的想法

第一次看到这题，我的第一反应就是：把所有可能的两个数组合都试一遍不就完了？

两层循环，外层遍历第一个数，内层遍历第二个数，检查它们的和是否等于 target。这是最"暴力"的方法，但也是最直观的：

javascript

var twoSum = function(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 []
}

时间复杂度 O(n²)，空间复杂度 O(1)。对于小数组来说完全没问题，但数组大了就会慢。

问题在哪？

仔细想想，这个方法其实做了很多重复工作。

当我们检查 nums[i] + nums[j] === target 时，我们已经知道了 nums[i] 和 target，所以 nums[j] 应该等于 target - nums[i]。但我们还是用循环去找这个值，这就是重复工作。

而且，如果我们需要快速查找"某个值是否在数组中"，用循环是 O(n)，但用哈希表（Map/Set）可以做到 O(1)。

换个思路

既然我们需要找的是 target - nums[i]，那能不能在遍历的时候，把已经见过的数字存起来，这样下次需要查找的时候就能直接找到了？

这就是哈希表的思路。我们可以用一个 Map 记录"值 -> 索引"的映射，遍历数组时：

计算 remain = target - nums[i]
检查 remain 是否在 Map 中
如果在，说明找到了，返回 [map.get(remain), i]
如果不在，把 nums[i] 存入 Map，继续遍历

关键点：先查找再存入。这样可以避免"同一个元素使用两次"的问题。比如 nums = [3, 3], target = 6，如果先存入再查找，遍历到第二个 3 时会错误地返回 [0, 0]。

javascript

var twoSum = function(nums, target) {
    const map = new Map()
    
    for (let i = 0; i < nums.length; i++) {
        const remain = target - nums[i]
        
        // 先查找，避免自匹配
        if (map.has(remain)) {
            return [map.get(remain), i]
        }
        
        // 再存入，供后续查找使用
        map.set(nums[i], i)
    }
    
    return []
}

这样时间复杂度降到了 O(n)，空间复杂度 O(n)。用空间换时间，这是查找问题的经典优化思路。

为什么这样能工作？

当我们遍历到 nums[i] 时，我们检查的是"之前是否见过 target - nums[i]"。如果见过，说明这两个数一个在前面（索引在 Map 中），一个在当前位置（索引是 i），直接返回即可。

如果没见过，继续遍历，把当前数存入 Map。这样后续遍历时，如果遇到能配对的数，就能直接找到了。

这道题在考什么？

这道题的核心是哈希表的应用。当我们需要快速查找"某个值是否出现过"时，哈希表是首选。用 O(n) 的空间换 O(n) 的时间，避免了嵌套循环。

下次遇到类似题目，看到"查找"、"是否存在"这些关键词，就应该想到哈希表。比如三数之和、四数之和这些题，虽然解法不同，但思路都是类似的。

记忆要点：

查找问题 → 哈希表
一次遍历 → 边遍历边查找
先查找再存入 → 避免自匹配

两数之和 ​

最直观的想法 ​

问题在哪？ ​

换个思路 ​