记一次面试中的算法题(两数之和)

前段时间,有次面试中遇到一道算法题,感觉答的不是很好,后面查相关资料发现竟然就是 LeeCode 上的原题。。。

题目是这样的,给定一个 int 数组,和 target 目标值,要求返回数组中两个数加起来等于 target 的这两个元素的下标,可以明确只会有一对能匹配上。

1
2
3
4
// 例如,给定:
int[] arr = new int[] { 1, 2, 3, 4, 7, 9, 8 };
int target = 13;
// 返回:3, 5

面试官问我题目理解清楚了吗?我心想:这还不简单,不就是两层循环判断一下就可以了嘛!于是二话不说,啪啪几分钟就写出了下面这段代码。

1
2
3
4
5
6
7
8
9
10
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 上的答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

更简便的写法:

1
2
3
4
5
6
7
8
9
10
11
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;
}

看来以后有时间还是要看看算法,不仅是为了面试,实际项目中也会遇到的,要写出高性能的程序,还是要靠这些。