LeetCode 1. 两数之和

约 4 分钟
文章信息 30 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 历史考题 200-500 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 小米 商汤 旷视 亚马逊 虾皮 携程 哔哩哔哩 作业帮 LeetCode 热题 100 面试经典 150 题
标签
数组 哈希表 nSum 问题
目录

题目描述

✅ 1. 两数之和

image-20230305151955963

题意分析

给定整数数组 nums 和目标值 target，返回两个不同下标，使这两个下标上的数之和等于 target。

三个约束决定了解法边界。其一，返回的是下标而不是数值，所以任何打乱顺序的预处理都必须把原下标带上。其二，同一个元素不能用两次，这在 target = 2 * nums[i] 时会成为真实陷阱。其三，数组无序且可能含重复值与负数，因此不能排序后直接二分，也不能靠数值去重。

关键转化：两数之和的本质是配对。固定当前元素 nums[i] 后，需要的另一个数被完全确定为 need = target - nums[i]，问题从「找两个数」降为「查一个数是否出现过」。查询用哈希表就是 $O(1)$。

再加一个观察：任何一组答案 (i, j) 且 i < j，都会在扫描到 j 时被发现——因为那时 i 已经在表里了。所以只朝历史方向查询就不会漏解，不需要双层枚举。

边界：题目保证恰好存在一个答案，所以不必处理无解；但代码结尾仍要有返回值以满足编译。

解法：一次遍历哈希表

核心思路

用哈希表记录已遍历元素的「值 → 下标」。遍历到 nums[i] 时查找补数 target - nums[i]；命中后直接返回两个下标。

必须先查再写，保证哈希表中只有当前元素之前的下标，不会重复使用同一个元素。

解题步骤

  • 创建空哈希表 indexByValue。
  • 遍历数组，计算补数 need = target - nums[i]。
  • 若补数已在表中，返回补数下标和当前下标。
  • 否则记录当前值及其下标，继续遍历。

代码实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexByValue = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            Integer j = indexByValue.get(need);
            if (j != null) {
                return new int[] {j, i};
            }
            indexByValue.put(nums[i], i);
        }

        return new int[0];
    }
}

func twoSum(nums []int, target int) []int {
    indexByValue := make(map[int]int)

    for i, num := range nums {
        need := target - num
        if j, ok := indexByValue[need]; ok {
            return []int{j, i}
        }
        indexByValue[num] = i
    }

    return []int{}
}

复杂度分析

  • 时间复杂度：$O(n)$，每个元素至多查询、写入哈希表一次。
  • 空间复杂度：$O(n)$，哈希表最多保存 $n$ 个元素。

关键点总结

  • 哈希表保存下标，而不是只记录元素是否存在。
  • 先查补数、后存当前值，既避免复用当前元素，也能正确处理重复值。
  • 命中即返回，无需继续遍历或额外排序。

易错点总结

  • 先存当前值再查补数，可能把同一元素使用两次。
  • 哈希表只存元素、不存下标，无法构造返回值。
  • 对重复值去重会漏掉 [3, 3] 这类合法答案。

相似题目

题目 难度 考察点
167. 两数之和 II - 输入有序数组 中等 输入已有序，双指针可省掉排序做到 $O(1)$ 空间
170. 两数之和 III - 数据结构设计 简单 转成数据结构设计，权衡 add 与 find 的复杂度分配
653. 两数之和 IV - 输入二叉搜索树 简单 中序遍历得到有序序列，或遍历时用哈希集合查补数
1099. 小于 K 的两数之和 简单 由等于改成小于，双指针在移动时顺带维护最优解
15. 三数之和 中等 排序后固定一个数 + 内层双指针，额外处理去重
454. 四数相加 II 中等 四数组分两半，用哈希表存前两组和的出现次数
888. 公平的糖果交换 简单 先由总和差推出目标差值，再退化为一次哈希查补数
面试题 16.24. 数对和 中等 要求返回全部数对，哈希需按数值计数而非命中即返回