这是整个LeetCode Hot 100 博客系列的第一篇，在这篇博客里，我会记录我自己的解题思路、代码实现，以及对这道题思想的总结。
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- 只会存在一个有效答案
暴力解法
这是最简单的解法了，基本是读完题目就能想到。既然题目要求从一个数组中获得两个整数相加求得目标值即可，那就直接用两个 for 循环。
class Solution {
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};
}
}
}
return new int[0];
}
}
这里由于使用了两个循环，所以时间复杂度来到了 O(n^2)，其中 N 代表数组中的元素个数。
这里可以使用 int 的原因是 Java 中 int 的取值范围为 -2^31 ~ 2^31-1（大约 -21亿 到 21亿），而题目中 10^9 和 -10^9 完全在这个范围内。在一些其他题目中，如果数字超过了 int 的范围，就需要改用 long，或者更大范围的 BigInteger 了。
使用哈希表
使用哈希表，可以将时间复杂度降低到 O(n)，我们只要进行一次循环即可。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++){
int choose = nums[i];
int diff = target - choose;
if(map.containsKey(diff)){
return new int[]{map.get(diff), i};
}
map.put(choose, i);
}
return new int[0];
}
}
注意： 这里需要先判断 containsKey 后才能 put 进去。如果你顺序反了，就可能出现：
nums[0] = 3。- 先执行
put：map变成了{3=0}。 - 计算
diff = 6 - 3 = 3。 - 执行
containsKey(3)：由于刚刚才把3放进去，这里返回true！ - 执行
return new int[]{map.get(3), 0}：由于map.get(3)是0，于是返回[0, 0]。
为什么说时间复杂度可以降低到 O(n) 呢？map.containsKey(diff) 这一步不要时间吗？
原因就是 HashMap 底层是一个数组（哈希桶），同时结合链表和红黑树用来提高性能和解决冲突。它通过计算 key 的哈希值，直接算出这个元素在数组里的下标（类似于 array[index]），而不需要像数组遍历那样一个个去比对。
也就是说，虽然 containsKey 涉及计算哈希、判断桶等步骤，但因为它不需要遍历，所以平均只需常量级的时间。因此：
时间复杂度 = 一次遍历 O(n) * 每次查找 O(1) = O(n)
另外，JDK 8 引入红黑树是为了解决哈希冲突严重时的性能问题。当多个元素映射到同一个桶时，链表会越来越长，查找效率从 O(1) 退化到 O(n)。当单个桶内的链表长度超过阈值时，会转为红黑树，把该桶内的查找复杂度从 O(n) 降到 O(logn)。当然，在算法题的常规数据规模下，我们通常默认哈希表查找是 O(1)。