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

【LeetCode 热题 100】1. 两数之和——（解法二）哈希表

web 2025/9/6 7:55:14

Problem: 1. 两数之和

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(N)

整体思路

这段代码旨在高效地解决 “两数之和” 问题。与 O(N^2) 的暴力枚举法相比，此版本采用了一种经典的 “空间换时间” 策略，利用 哈希表 (HashMap) 将时间复杂度优化到了线性级别 O(N)。

该算法的核心思想是，在遍历数组的同时，利用哈希表快速查找每个数字所需的“另一半”。

算法的逻辑步骤可以分解如下：

数据结构选择：
- 算法选择 HashMap 作为核心数据结构。这个哈希表将用于存储已经遍历过的数字及其对应的索引，即 (数字 -> 索引) 的键值对。
- 目的：哈希表提供了平均时间复杂度为 O(1) 的查找操作。这使得我们能够即时地回答“我们之前是否见过某个数字？”这个问题。
单次遍历与查找：
- 算法只需对 nums 数组进行一次 for 循环遍历。
- 在循环的每一步（对于当前数字 nums[i]），算法执行两个核心操作，且顺序非常关键：
  a. 计算并查找“补数”：首先，计算出要与 nums[i] 相加才能得到 target 的那个“补数” other，即 other = target - nums[i]。然后，算法立即在哈希表中检查是否存在这个 other。
  b. 处理查找结果：
  - 如果找到了 (map.containsKey(other))：这意味着 other 这个数字在数组的前面部分（0 到 i-1 的索引中）已经出现过。我们已经找到了解！此时，直接返回 other 的索引（从哈希表中获取 map.get(other)）和当前数字的索引 i。
  - 如果没有找到：这意味着在已经遍历过的数字中，没有 nums[i] 的“另一半”。那么，nums[i] 本身可能就是未来某个数字的“另一半”。因此，算法将当前数字 nums[i] 及其索引 i 存入哈希表中，以供后续的迭代查找。
返回结果：
- 由于题目保证有且仅有一个解，if 条件一定会在某个时刻被满足并返回结果。因此，理论上最后的 return null; 是不可达的（但在语法上是必需的，以防编译器报错）。

通过这种“边遍历边记录”的方式，算法将寻找配对数的过程从 O(N) 的线性扫描缩短为 O(1) 的哈希查找，从而实现了整体性能的飞跃。

完整代码

import java.util.HashMap;
import java.util.Map;class Solution {/*** 在数组中找出和为目标值的两个数的索引。* @param nums 整数数组* @param target 目标和* @return 包含两个索引的数组，如果不存在则返回 null*/public int[] twoSum(int[] nums, int target) {int n = nums.length;// map: 用于存储已遍历过的数字及其索引。// Key: 数组中的数字// Value: 该数字对应的索引Map<Integer, Integer> map = new HashMap<>();// 单次遍历数组for (int i = 0; i < n; i++) {// 计算当前数字 nums[i] 需要配对的“另一半”int other = target - nums[i];// 关键步骤：检查“另一半”是否已经存在于哈希表中// 这是 O(1) 的高效查找操作if (map.containsKey(other)) {// 如果存在，说明我们找到了解。// map.get(other) 是“另一半”的索引，i 是当前数字的索引。return new int[]{map.get(other), i};}// 如果“另一半”不存在，则将当前数字和它的索引存入哈希表，// 以便后续的元素可以查找它作为配对。map.put(nums[i], i);}// 根据题目假设，总会有一个解，所以理论上不会执行到这里。return null;}
}

时空复杂度

时间复杂度：O(N)

循环：算法的核心是一个 for 循环，它严格地遍历 nums 数组一次。如果数组的长度为 N，这个循环将执行 N 次。
循环内部操作：
- 在循环的每一次迭代中，执行的主要操作是 map.containsKey() 和 map.put()。
- 对于 HashMap，这两个操作的平均时间复杂度都是 O(1)。
- 其余的算术和赋值操作也是 O(1)。