LeetCode之旅——Two Sum，哈希表的應用

今天做的題叫Two Sum，簡單題，給定一個整形數組和一個整數target，存在唯一的兩個成員相加等於target，要求返回這兩個成員的位置。

示例：

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解決方案

1. 暴力算法

最簡單的當然是暴力算法，一個嵌套的for循環搞定。標準答案如下：

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
}

2. 哈希表

第一種方法的時間復雜度是O(n²)，空間復雜度O(1)。另一個更快的解決方案是利用哈希表。遍歷數組並將成員其插入哈希表，再查詢[target - 成員]是否在表中（不能等於自身），如果在則結果已產生。至於是一次遍歷實現還是兩次遍歷個人認為區別不大。
標準答案如下：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
}

總結

哈希表最大的優勢在於查詢。理想的哈希表可以以O(1)的時間復雜度處理查詢。此題的微妙之處在於，需要將數組索引作為表的值而數組成員作為鍵。而思維慣性可能讓人一時轉不過彎。

哈希表雖然高效，但卻不是任何時候都適用。它的空間復雜度是O(n)，但其常數因子並不小，可能花費甚至浪費很大的空間。另外衝突處理也會一定程度降低哈希表的性能。

因此哈希表並不總是比暴力解法好。如果你的空間足夠，數據量大，查詢頻度高，我認為使用哈希表是合理的選擇。