前段時間，有次面試中遇到一道算法題，感覺答的不是很好，后面查相關(guān)資料發(fā)現(xiàn)竟然就是LeeCode上的原題。。。

題目是這樣的，給定一個int數(shù)組，和target目標值，要求返回數(shù)組中兩個數(shù)加起來等于target的這兩個元素的下標，可以明確只會有一對能匹配上。

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

面試官問我題目理解清楚了嗎？我心想：這還不簡單，不就是兩層循環(huán)判斷一下就可以了嘛！于是二話不說，啪啪幾分鐘就寫出了下面這段代碼。

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;
}

給面試官看后，問我這種實現(xiàn)的時間復雜度是多少？我說最壞的情況應該是O(n2)。他問還有其它更快的實現(xiàn)方式嗎？讓我再想想。

看來他對我這個實現(xiàn)不是很滿意，也是，咋可能有這么簡單的題，然而想了幾分鐘后還是一點頭緒沒有。。。

最后面試掛了，不知道是不是掛在這道題上。后來無意中在LeeCode上看到原題才恍然大悟?。?！

其實就是以空間換時間，用HashMap把數(shù)存起來，通過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;
}

看來以后有時間還是要看看算法，不僅是為了面試，實際項目中也會遇到的，要寫出高性能的程序，還是要靠這些。