前段时间，有次面试中遇到一道算法题，感觉答的不是很好，后面查相关资料发现竟然就是LeeCode上的原题。。。
题目是这样的，给定一个int数组，和target目标值，要求返回数组中两个数加起来等于target的这两个元素的下标，可以明确只会有一对能匹配上。
// 例如，给定：
int[] arr = new int[] { 1, 2, 3, 4, 7, 9, 8 };
int target = 13;
// 返回：3, 5
面试官问我题目理解清楚了吗？我心想：这还不简单，不就是两层循环判断一下就可以了嘛！于是二话不说，啪啪几分钟就写出了下面这段代码。
public int[] sum(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if ((arr[i] + arr[j]) == target) {
return new int[] { i, j };
}
}
}
return null;
}
给面试官看后，问我这种实现的时间复杂度是多少？我说最坏的情况应该是O(n2)。他问还有其它更快的实现方式吗？让我再想想。
看来他对我这个实现不是很满意，也是，咋可能有这么简单的题，然而想了几分钟后还是一点头绪没有。。。
最后面试挂了，不知道是不是挂在这道题上。后来无意中在LeeCode上看到原题才恍然大悟！！！
其实就是以空间换时间，用HashMap把数存起来，通过Hash查找方式减少一层遍历，因为Hash理论上时间负责度是O(1)，从而将总的时间复杂度从O(n2)降到O(n)。
附LeeCode上的答案：
public int[] sum(int[] arr, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
for (int i = 0; i < arr.length; i++) {
int complement = target - arr[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
return null;
}
更简便的写法：
public int[] sum(int[] arr, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int complement = target - arr[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(arr[i], i);
}
return null;
}
看来以后有时间还是要看看算法，不仅是为了面试，实际项目中也会遇到的，要写出高性能的程序，还是要靠这些。
