两数之和

一、题目（LeetCode 1 · 简单 · Hot100）

给定一个整数数组 nums 和一个整数目标值 target，找出和为 target 的两个整数，返回它们的数组下标。每种输入恰好对应一个答案，同一元素不能重复使用，答案顺序任意。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]      // nums[0] + nums[1] == 9

二、思路演进

2.1 暴力：枚举所有两数组合

双重循环枚举 (i, j)，判断 nums[i] + nums[j] == target：

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (nums[i] + nums[j] == target) return new int[]{i, j};

为什么不够：n 个数有 n(n-1)/2 个组合，10^4 个元素就是约 5×10^7 次比较，实测超时。更本质的问题是——每来一个新数，都在重复回答同一个问题："数组里有没有某个值"。这个查询本可以一次 O(1) 完成。

2.2 关键洞察：用哈希把"查询另一半"变成 O(1)

站在遍历中的 nums[i] 的角度，它要找的另一半是确定的：target - nums[i]。

问题从"两两求和"被改写成"逐个查询"——查询正是哈希表的强项。于是边遍历边建表：

• 走到 nums[i] 时，先查表里有没有 target - nums[i]；有就直接出答案；
• 没有再把 nums[i] 自己放进表（值 → 下标），等后面的数来配对。

一遍扫完，每个元素只被"查一次、放一次"。这是"空间换时间"最短路径的教科书案例，也是 字母异位词分组 里"为分组设计 key"的前置直觉。

三、复杂度分析

• 时间 O(n)：每个元素至多经历一次 get、一次 put，都是均摊 O(1)。对比暴力的 O(n²)，本质是拿一个 O(n) 的 map 把内层循环整体消掉。
• 空间 O(n)：最坏情况（答案在最后两个元素）表里存了 n-1 个键值对。

四、代码

package org.example;

import java.util.HashMap;
import java.util.Map;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_1 {

    public static void main(String[] args) {
        int[] ans = twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println(ans[0] + " " + ans[1]);          // 期望 0 1

        // 重复元素 + target 恰为两倍：考察"先查后放"是否正确
        int[] ans2 = twoSum(new int[]{3, 3}, 6);
        System.out.println(ans2[0] + " " + ans2[1]);        // 期望 0 1
    }

    public static int[] twoSum(int[] nums, int target) {
        // key = 数值，value = 下标；记录"已经见过谁"
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 先查：我的另一半来过没有
            Integer j = seen.get(target - nums[i]);
            if (j != null) {
                return new int[]{j, i};
            }
            // 后放：避免 target = 2x 时元素自己配自己
            seen.put(nums[i], i);
        }
        return new int[0];
    }

}

五、坑点

• 先查后放的顺序：先 put 再查，[3] + target=6 会拿 3 自己匹配自己；边查边放天然规避。
• 返回的是下标不是值：这也是"不能先排序再双指针"的直接原因。排序会打乱下标（除非额外存原下标）。
• 重复元素是合法输入：[3,3] 中后出现的 3 查表时能查到先出现的 3，逻辑无需特判。
• get 的拆箱 NPE：用 Integer j = map.get(...) 判空，别写 int j = map.get(...)，不存在时直接 NPE。
• 溢出提醒：本题数值范围小；若数值贴着 int 极限，target - nums[i] 理论上会溢出，改用 nums[i] + nums[j] == target 逆向判断可避开。

六、变形追问

• 变体一（输入已升序）：LeetCode 167「两数之和 II」。此时不必用哈希：首尾对撞双指针，和大了右端退、小了左端进，O(n) 时间 O(1) 空间。与 盛最多水的容器 同款的"排除法"双指针。
• 变体二（要所有解）：哈希改成 值 → 下标列表，或改用排序 + 双指针扫出全部组合，同值段注意去重计数。

2026-10 新增（E 轨 · Hot100 第一批）。