href="https://www.cnblogs.com/ljbguanli/p/19621851"

title="发布于

aria-level="2">【Hot100-Java便捷】：两数之和

(Two

id="content_views">

1.

题目回顾

题目描述：

给定一个整数数组

nums

整数，并返回它们的数组下标。

约束条件：

• 每种输入只会对应一个答案。

• 数组中同一个元素在答案里不能重复出现。

• 可以按任意顺序返回答案。

示例：

Force)

这是最直观的解题思路。

这就好比我们在一个房间里找两个人，我们先拉住第1个人，然后去问剩下的所有人：“你是那个能和我配对的人吗？

”如果不是，再拉住第2个人，重复这个过程。

思路与算法

1. 枚举数组中的每一个数

   x（作为第一个加数）。

2. 在

   x

   x（作为第二个加数）。

3. 一旦找到，立即返回两个数的下标。

代码实现

Java

复杂度分析

• 时间复杂度：

  alt="$O(N^2)$"

  src="https://latex.csdn.net/eq?%24O%28N%5E2%29%24">

  其中

  src="https://latex.csdn.net/eq?%24N%24">

  是数组元素的数量。

  最坏情况下，我们需要遍历几乎所有的元素对。

  当数据量较大（例如

  src="https://latex.csdn.net/eq?%24N%3D10000%24">）时，计算量会达到

  1亿次级别，效率较低。

• 空间复杂度：

  alt="$O(1)$"

  src="https://latex.csdn.net/eq?%24O%281%29%24">。

  除了存储变量，不需要额外的内存空间。

---

3.

方法二：哈希表

性能的飞跃

暴力法慢在哪里？

慢在“寻找”。

我们在数组中寻找

target

src="https://latex.csdn.net/eq?%24O%281%29%24">

(Hash

Map)。

思路与算法

我们可以把哈希表想象成一个“备忘录”。

在遍历数组时，对于每一个数

nums[i]：

1. 我们先算一下：为了凑齐

   need

   nums[i]）。

2. 查备忘录：看看之前遍历过的数字里，有没有这个

   need？

   • 如果就在备忘录里：太好了，说明之前遇到过那个数，直接把它的下标拿出来，和当前的

     i

     一起返回。

   • 如果不在：把当前的数

     nums[i]

     记入备忘录，方便后面的数字来找我匹配。

代码实现

Java

Key存数值，Value存下标HashMap

integer="">

查备忘录：看需要的那个数是否存在if(map.containsKey(need)){//

new

复杂度分析

• 时间复杂度：

  alt="$O(N)$"

  src="https://latex.csdn.net/eq?%24O%28N%29%24">。

  我们只需要遍历一次数组。

  在哈希表中查找元素的时间复杂度平均为

  $O(1)$。

• 空间复杂度：

  alt="$O(N)$"

  src="https://latex.csdn.net/eq?%24O%28N%29%24">。

  我们需要一个哈希表来存储已经遍历过的元素，最坏情况下需要存储

  $N$

  总结与对比

特性	暴力枚举法	哈希表法
核心思想	穷举所有组合	边查边存（以空间换时间）
时间复杂度	alt="$O(N^2)$" src="https://latex.csdn.net/eq?%24O%28N%5E2%29%24"> (慢)	src="https://latex.csdn.net/eq?%24O%28N%29%24"> (快)
空间复杂度	alt="$O(1)$" src="https://latex.csdn.net/eq?%24O%281%29%24"> (省内存)	src="https://latex.csdn.net/eq?%24O%28N%29%24"> (耗内存)
适用场景	数据量极小，内存极其受限	通用场景，追求运行速度