1、两数之和
1、两数之和
题意
给出一个数组和一个目标值，让你在数组中找出和为目标值的两个数，并且这两个数在数
组中的下标（索引）不同。
示例
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
难度
简单
分析
我相信，大部分球友都能想到暴力破解，即便你是算法小白，以前从来没有刷过
LeetCode。
当然了，没有一点 Java 基础肯定是不行的，所以推荐你先去看看二哥的 Java 进阶之路，
最起码刷一个星期把语法先掌握了。
001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C-20231209084508.png
好，所谓的“暴力”，在算法领域表示“穷举、极低效率的实现”。主要源于这个英文单词
（Brute-Force，暴力攻击）。
两层遍历，第一层确定第一个数，第二层确定第二个数，用一个加法运算就可以完成题目
的要求。
class Solution {
// 定义一个方法 twoSum，接收一个整数数组 nums 和一个目标值 target
public int[] twoSum(int[] nums, int target) {
// 外层循环遍历数组中的每个元素
for(int i = 0; i < nums.length; i++) {
// 内层循环从当前元素的下一个开始遍历
for(int j = i + 1; j < nums.length; j++) {
// 检查当前选中的两个数之和是否等于目标值
if(nums[i] + nums[j] == target)
// 如果等于目标值，返回这两个数的索引
return new int[]{i, j};
}
}
// 如果遍历完数组都没有找到符合条件的两个数，则抛出异常
throw new IllegalArgumentException("没有找到");
}
}
笔试如果遇到不太会的题，就暴力。不过两次遍历的时间复杂度是 $ O(n^2) $。
时间复杂度，在算法领域是一个非常重要的概念，一个衡量算法执行时间随输入数据规模
增长而增长的度量。在这个特定的 “两数之和” 问题的解法中，时间复杂度是由两层嵌套
循环决定。
我在二哥的 Java 进阶之路里有详细地解释过，戳链接了解。
$ O(n^2) $ 的时间复杂度实在是太不理想，效率太低，在所有 Java 提交中只能击败不到
28% 的用户。
001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C-20231209085119.png
能不能优化一下呢？
观察第二个循环，我们是从每个 i 后面开始找，找一个与之相加等于目标值 target 的数。
反过来想，能不能判断每个 i 前面的数是否存在与之相加等于目标值 target 的呢？
可能你会脑袋一热写出下面这样的代码：
class Solution {
// 定义一个方法 twoSum，接收一个整数数组 nums 和一个目标值 target
public int[] twoSum(int[] nums, int target) {
// 外层循环遍历数组中的每个元素
for(int i = 0; i < nums.length; i++)
// 内层循环从数组的开始到当前元素之前遍历
for(int j = 0; j < i; j++)
// 检查当前选中的两个数之和是否等于目标值
if(nums[i] + nums[j] == target)
// 如果等于目标值，返回这两个数的索引
return new int[]{i, j};
// 如果遍历完数组都没有找到符合条件的两个数，则抛出异常
throw new IllegalArgumentException("没找到");
}
}
虽然击败了 33% 的 Java 选手，但是这样的算法时间复杂度和之前相比根本没有变化。
001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C-20231209085742.png
我们反推一下。
已知 i 和 target，那么 target - i 就是与 i 相配对的另一个数，我们只需要判断 target - i
是否在 i 之前出现过，如果出现过，那么这两个数就是我们要找的数。
那么问题来了，如何判断 target - i 是否在 i 之前出现过呢？
我们可以用一个 HashMap 来记录数组中的每一个元素，元素的索引作为哈希表的 key，
元素本身作为 value，当发现 target - i 在哈希表中存在时，就可以直接返回这两个数的索
引了。来看题解。
class Solution {
// 定义一个方法 twoSum，接收一个整数数组 nums 和一个目标值 target
public int[] twoSum(int[] nums, int target) {
// 创建一个哈希表来存储数组元素和它们的索引
Map<Integer, Integer> map = new HashMap<>();
// 遍历数组中的每个元素
for(int i = 0; i < nums.length; i++){
// 计算与当前元素相配对的另一个元素的值
int complement = target - nums[i];
// 检查哈希表中是否已存在这个配对元素
if(map.containsKey(complement))
// 如果存在，返回当前元素的索引和配对元素的索引
return new int[]{i, map.get(complement)};
// 将当前元素及其索引添加到哈希表中
map.put(nums[i], i);
}
// 如果遍历完数组都没有找到符合条件的两个数，则抛出异常
throw new IllegalArgumentException("没找到");
}
}
当输入是 nums = [2,7,11,15] 和 target = 9 时，我们来模拟上述解决 “两数之和” 的整个
过程：
1. 初始化哈希表：开始时，哈希表为空。
2. 遍历数组：
– 第一个元素（i = 0）：nums[0] = 2
• 计算 complement = target - nums[i] = 9 - 2 = 7。
• 检查哈希表中是否存在 7。目前哈希表为空，所以不存在。
• 将 (2, 0) 加入哈希表（值为 2，索引为 0）。
– 第二个元素（i = 1）：nums[1] = 7
• 计算 complement = 9 - 7 = 2。
• 检查哈希表中是否存在 2。是的，它存在，并且索引为 0。
• 找到匹配的一对元素：nums[0] = 2 和 nums[1] = 7，它们的和为 9。
• 返回这两个元素的索引 [1, 0]。
因此，对于输入 nums = [2,7,11,15] 和 target = 9，该题解会返回 [1, 0] 作为结果，表
示 nums 数组中索引为 1 和 0 的元素相加得到目标值 9。
时间复杂度：$ O(n) $
空间复杂度：$ O(Max{nums[i]}) $
哦吼，这次结果就不一样了，打败了 71% 的选手，效果显著。
001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C-20231209091539.png
总结
对于本题，我们用到了 Java 中的一个普通 for 循环，和一个 HashMap，这两个都是 Java
中必须掌握的知识，如果你对这两个都不熟悉，那么你的 Java 基础还是不够扎实。
建议通过下面三个链接来学习（带上数组）：
• Java for 循环
• 数组
• HashMap
力扣链接：https://leetcode.cn/problems/two-sum/