当前位置：首页 > news >正文

LeetCode 热题100 - 1. 两数之和（Java 题解）

news 2026/6/18 4:56:41

LeetCode 热题100 - 1. 两数之和（Java 题解）

题目链接

两数之和 - LeetCode

难度

简单

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

注意：

每种输入只会对应一个答案。
数组中同一个元素在答案里不能重复出现。
可以按任意顺序返回答案。

解题思路

本题最优解为「哈希表法」，核心思路是「空间换时间」，解决暴力解法效率低的问题，具体思路如下：

暴力解法分析：双重循环遍历所有数对，判断两数之和是否等于 target，时间复杂度 O(n²)，对于大数据量效率极低，不推荐用于面试和实际提交。
哈希表优化逻辑：要找到两数之和为 target，等价于对数组中的每个元素 nums[i]，寻找 target - nums[i]（即补数）是否存在于数组中，且补数的下标不等于 i。
具体操作：使用 HashMap 存储已遍历过的元素，key 为元素值，value 为元素对应的下标，这样可以将「查找补数」的操作从 O(n) 优化到 O(1)。
遍历流程：遍历数组时，先计算当前元素的补数，判断补数是否在 HashMap 中；若存在，直接返回当前下标和补数的下标；若不存在，将当前元素和其下标存入 HashMap，继续遍历。

复杂度分析

时间复杂度：O(n)，仅遍历数组一次，每次 HashMap 的查找、插入操作均为 O(1)。
空间复杂度：O(n)，最坏情况下，需要将数组中所有元素存入 HashMap（即答案在数组末尾）。

解题代码（Java）

import java.util.HashMap;
import java.util.Map;public class Solution {public int[] twoSum(int[] nums, int target) {// 哈希表：key=数组元素值，value=元素对应的下标Map<Integer, Integer> map = new HashMap<>();int length = nums.length;// 遍历数组，一次完成查找和存入操作for (int i = 0; i < length; i++) {// 计算当前元素需要的补数（target - 当前元素）int sub = target - nums[i];// 判断补数是否已在哈希表中（已遍历过）if (map.containsKey(sub)) {// 存在则直接返回结果，顺序不影响题目要求return new int[]{i, map.get(sub)};}// 不存在则将当前元素和下标存入哈希表，供后续元素查找map.put(nums[i], i);}// 题目保证有唯一解，此处仅为满足语法完整性，不会执行到return null;}
}

代码解析

HashMap 定义：Map<Integer, Integer> map = new HashMap<>()，专门用于缓存已遍历的元素和其下标，避免重复遍历。
补数计算：int sub = target - nums[i]，这是本题的核心逻辑，将“两数之和”转化为“单个数查找补数”。
补数判断：map.containsKey(sub)，快速判断补数是否存在，时间复杂度 O(1)，这是哈希表优化的关键。
结果返回：找到补数后立即返回，无需继续遍历，提升代码执行效率；返回的下标顺序可颠倒，题目不做要求。
兜底返回：return null 仅为语法要求，题目明确每种输入有唯一解，遍历过程中一定会找到答案并返回。

示例演示

输入：nums = [2,7,11,15], target = 9

i=0，nums[0]=2，sub=9-2=7，HashMap 为空，存入 (2, 0)；
i=1，nums[1]=7，sub=9-7=2，HashMap 包含 key=2，返回 [1, 0]；
程序结束，输出结果 [1, 0]（或 [0, 1] 均正确）。

易错点提醒

不能先将当前元素存入 HashMap，再判断补数：否则会出现“自己和自己配对”的情况（如 nums = [3,2,4], target=6，若先存 3，再判断 sub=3，会误返回 [0,0]）。
HashMap 的 key 存元素值、value 存下标：因为我们需要通过“补数（值）”查找对应的下标，而非通过下标查找值。
无需考虑数组元素重复：题目明确“每种输入只会对应一个答案”，且“同一个元素不能重复出现”，因此重复元素不会影响结果。