两数之和 图解题解

这道题真正在问什么

题目给一个数组 nums 和一个目标值 target，要找出两个不同下标 i、j，使 nums[i] + nums[j] 恰好等于 target，返回这两个下标。题目保证恰好存在一组答案，且同一个元素不能用两次。注意要返回的是下标而不是数值本身——这个细节决定了后面「排序再找」的路子并不划算，因为排序会打乱原始下标。

为什么暴力两层循环会慢

最直觉的做法是两层循环：外层固定一个数，内层把它后面的每个数都试一遍，看相加是否等于 target。数组有 n 个数时，最坏要试大约 n²/2 对组合，时间复杂度 O(n²)。慢的根源在于「找搭档」这一步是线性扫描：每固定一个数，都要把剩下的数从头到尾翻一遍。

换个角度想，当我们站在某个数 x 面前时，其实完全知道要找的搭档是谁——就是 target - x 这个确定的值。问题只剩下一件事：怎么用比线性扫描更快的方式，判断这个值有没有出现过。

为什么两数之和要用哈希表

「判断某个值出现过没有、出现在哪」正是哈希表（散列表）最擅长的事：插入和查询平均都是 O(1)。于是解法自然成形——建一张表记录「已经见过的值 → 它的下标」，从左到右扫数组，每到一个数 x 就先问表：target - x 在不在？在，说明搭档早就出现过，直接返回它记录的下标和当前下标；不在，就把 x 和它的下标存进表，继续往右走。

这样原来内层循环的整段线性扫描，被压缩成了一次 O(1) 的查表。n 个数每个只查一次、至多存一次，总时间就从 O(n²) 降到 O(n)，代价是一张最多存 n 个数的表，空间 O(n)——用空间换时间的经典交易。

为什么必须先查再存，顺序不能反

循环体内「查 target - x」在前、「存 x」在后，这个顺序是正确性的关键。因为查的对象永远是「当前数左边已经出现过的数」，当前数还没入表，天然不可能查到自己——即使 target 恰好等于 2x，也不会误用同一个元素两次。

反过来，如果先把所有数一股脑存进表再来查，当 target - x 恰好等于 x 本身、而 x 只出现一次时，查到的其实是自己，会返回同一个下标两次，答案就错了。先查后存还有一个附带好处：找到答案的那一刻当前数根本不用入表，循环直接结束。

复杂度怎么算，边界在哪里

时间 O(n)：数组扫一遍，每个数做一次哈希查询、至多一次哈希写入，均摊都是 O(1)。空间 O(n)：最坏情况答案在最后一对，前面的数几乎全部进表。

两个容易踩的坑：一是哈希表的键值方向——键存「数值」、值存「下标」，因为我们是拿值反查下标，存反了就查不到；二是如果数组本身有序，更省内存的做法是左右对撞双指针，O(n) 时间、O(1) 空间（LeetCode 167 就是这个变体），但本题数组无序且要原始下标，哈希表一次遍历是最直接的答案。

Python

def twoSum(nums, target):
    seen = {}                    # 值 -> 下标
    for i, x in enumerate(nums):
        need = target - x        # 还差的另一半
        if need in seen:         # 另一半见过了
            return [seen[need], i]
        seen[x] = i              # 没配上，存自己
    return []

C++

vector<int> twoSum(vector<int>& nums, int target){
    unordered_map<int,int> seen;      // 值 -> 下标
    for(int i = 0; i < nums.size(); i++){
        int need = target - nums[i];
        auto it = seen.find(need);
        if(it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;            // 没配上，存自己
    }
    return {};
}

Java

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>(); // 值 -> 下标
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];   // 还差的另一半
        if (seen.containsKey(need)) {   // 另一半见过了
            return new int[]{seen.get(need), i};
        }
        seen.put(nums[i], i);          // 没配上，存自己
    }
    return new int[0];
}