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

LeetCode 1. 两数之和（Java）

news 2025/5/7 10:46:15

LeetCode 1. 两数之和（暴力 vs 哈希表）

题目描述

给定一个整数数组 nums 和一个整数 target，要求找出数组中和为目标值的两个数，并返回它们的下标。假设每个输入只有一种答案，且同一元素不能重复使用。

示例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：nums[0] + nums[1] = 2 + 7 = 9

解题思路

两种核心解法：

暴力循环法：双重遍历所有可能的组合，找到和为 target 的两个数。
哈希表法：利用哈希表存储“补数”，将时间复杂度优化到 O(n)。

方法一：暴力循环法

直接遍历数组中的每一对组合，检查它们的和是否等于 target。
时间复杂度：O(n²)
空间复杂度：O(1)

public int[] twoSum_1(int[] nums, int target) {int[] result = new int[2];for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[i] + nums[j] == target) {result[0] = i;result[1] = j;return result; // 找到后立即返回}}}return result;
}

代码优化点：

找到答案后立即返回，减少不必要的循环。
内层循环从 i+1 开始，避免重复检查 (i,j) 和 (j,i)。

缺点：
当数组长度较大时（例如 n=10^4），需要循环约 5×10^7 次，性能较差。

方法二：哈希表法

核心思想：用空间换时间。

遍历数组，将每个数及其索引存入哈希表。
再次遍历数组，检查 target - nums[i] 是否存在于哈希表中，并确保不是当前元素本身。

时间复杂度：O(n)
空间复杂度：O(n)（哈希表存储所有元素）

public int[] twoSum_2(int[] nums, int target) {HashMap<Integer, Integer> map = new HashMap<>();// 第一次遍历：存储所有元素及其索引for (int i = 0; i < nums.length; i++) {map.put(nums[i], i);}// 第二次遍历：查找补数for (int i = 0; i < nums.length; i++) {int temp = target - nums[i];if (map.containsKey(temp) && map.get(temp) != i) {return new int[]{i, map.get(temp)}; // 直接返回结果}}return new int[2];
}

关键点解释：

补数：即 temp = target - nums[i]，若 temp 存在于哈希表中，则说明找到答案。
避免重复使用同一元素：通过 map.get(temp) != i 确保两个下标不同。
哈希表的覆盖问题：若数组中有重复元素（如 nums = [3,3]），后一个元素的索引会覆盖前一个。但由于题目保证只有一个答案，覆盖不影响结果正确性。

示例分析（以 nums = [3,3], target = 6 为例）：

第一次遍历后，哈希表存储为 {3 → 1}（后面的 3 覆盖了前面的 3）。
第二次遍历时，i=0，计算 temp = 6-3=3，哈希表中存在且 map.get(3)=1 ≠ 0，返回 [0,1]。

哈希表法的优化

可以合并两次遍历为一个循环，边存边查：

public int[] twoSum_2_optimized(int[] nums, int target) {HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int temp = target - nums[i];if (map.containsKey(temp)) {return new int[]{map.get(temp), i};}map.put(nums[i], i); // 先查后存，避免同一元素被重复使用}return new int[2];
}