力扣热题100刷题-hash-1-两数之和

1 两数之和

题意

给定一个整数数组 nums 和一个目标值 target，找出数组中两个数，使它们的和等于 target，并返回它们的下标。

---

思路

一开始最自然的想法是双重循环，枚举所有两数组合，看是否等于 target。

时间复杂度 O(n^2)，数据量大时会超时。

优化思路：
在遍历数组时，记录已经遍历过的数字。
对于当前数字 x，只需要看 target - x 是否已经出现过。

因此可以使用 HashMap：

• key：数组中的值
• value：该值对应的下标

遍历一次数组即可解决。

---

易错点 / 卡点

• 第一想法： 双重 for 循环暴力枚举。

• 为什么不行： 时间复杂度 O(n^2)，不满足优化要求。

• 最终解法： 使用 HashMap，在一次遍历中完成查找。

• 容易出错点：

  • 先判断 complement 是否存在，再 put 当前值。
  • 注意数组中可能有重复元素。
  • 返回的是下标，不是数值。

---

核心思路（本质）

• 空间换时间
• “查找某个值是否存在” → 使用 HashMap
• 一边遍历，一边建立映射关系

本质是：
把 O(n) 的查找嵌入到一次遍历中，避免双重循环。

---

总结

看到“找两个数之和等于 target” + “只需返回一组解”， 立刻想到用 HashMap 记录已遍历元素，用空间换时间。