记一次面试中的算法题（两数之和）

前段时间，有次面试中遇到一道算法题，感觉答的不是很好，后面查相关资料发现竟然就是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;
}

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