来看看这道算法题（摘自LeetCode）：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
翻译成中文：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9，
因为 nums[0] + nums[1] = 2 + 7 = 9，
所以返回 [0, 1]。
一、暴力算法
面对这道题的时候，你会使用什么样的算法呢？是对数组进行两次暴力遍历来解决问题吗？或者有其他更有的算法？让我们先来看看简单的暴力算法。
public int[] numbers = {2, 7, 11, 15};
public final int target = 9;
public int[] getResult() {
int[] result = new int[2];//执行1次
int n = numbers.length;//执行1次
for (int i = 0; i < n; i++) {//执行n + 1次
for (int j = i + 1; j < n; j++) {//执行n + (n - 1) + (n -2) + (n - 3) ... + 1次，即1/2 * (n + 1) * n次
if (numbers[i] + numbers[j] == target) {//执行(n - 1) + (n -2) + (n - 3) ... + 1次，即1/2 * n * (n - 1)次
result[0] = i;//执行1次
result[1] = j;//执行1次
}
}
}
return result;//执行1次
}
对这个方法进行复杂度分析，我们进行了两轮遍历，如注释，其算法时间复杂度为O(n^2)。
再考虑其空间复杂度，当numbers的长度无限增大时，其运行过程中临时占用的存储空间始终保持不变，因此算法空间复杂度为O(1)。
二、哈希表算法
为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。
通过以空间换取速度的方式，我们可以将查找时间从O(n)降低到O(1)。哈希表正是为此目的而构建的，它支持以近似恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现碰撞冲突，查找用时可能会退化到 O(n)。
那么基于上述思想，算法的核心操作是将数组转换为HashMap。在这个示例中，我们把target换成22，算法代码如下：
public int[] numbers = {2, 7, 11, 15};
public final int target = 22;
public int[] getResult() {
int[] result = new int[2];//执行1次
Map<Integer, Integer> map = new HashMap<>();//执行1次
int n = numbers.length;//执行1次
for (int i = 0; i < n; i++) {//执行n + 1次
map.put(numbers[i], i);//执行n次
}
for (int i = 0; i < n; i++) {//执行n + 1次
int rest = target - numbers[i];//执行n次
if (map.containsKey(rest) && map.get(rest) != i) {//执行n次
result[0] = i;//执行1次
result[1] = map.get(rest);//执行1次
}
}
return result;//执行1次
}
此时算法的时间复杂度为O(n)，我们把包含有n个元素的数组遍历了两次。由于哈希表将查找时间“近似”缩短到 O(1) ，所以时间复杂度为O(n)。还是用“近似”，那是因为需要考虑哈希表发生碰撞的情况。
空间复杂度为O(n)，因为此算法需要额外开辟空间存储一个新的哈希表，该表中存储了n个元素。
注意，细心的读者会问为什么在if判断条件中增加了map.get(rest) != i这个条件。
这是为什么呢？前文我们已经将target换成了22，那么如果缺少这个判断条件，就可能找出两对组合，[7，15]和[11，11]，很明显，[11，11]是错误的组合，原因就是因为缺乏了map.get(rest) != i这个条件，即map.get(rest)不可以等于numbers[i]本身。
在这里我们将数组遍历了两次，可不可以遍历一次就满足需求呢？来看一下更加优美的算法实现：
public int[] numbers = {2, 7, 11, 15};
public final int target = 22;
public int[] getResult() {
int[] result = new int[2];//执行1次
int n = numbers.length;//执行1次
Map<Integer, Integer> map = new HashMap<>();//执行1次
for (int i = 0; i < n; i++) {//执行n + 1次
int rest = target - numbers[i];//执行n次
if (map.containsKey(rest)) {//执行n次
result[0] = map.get(rest);//执行1次
result[1] = i;//执行1次
}
map.put(numbers[i], i);//执行n次
}
return result;//执行1次
}
此时算法的时间复杂度为O(n)，空间复杂度为O(n)，与上文的哈希表算法一致，但是只遍历了一遍数组就完成了查找。
网友评论