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)，但其常数因子并不小，可能花费甚至浪费很大的空间。另外冲突处理也会一定程度降低哈希表的性能。

因此哈希表并不总是比暴力解法好。如果你的空间足够，数据量大，查询频度高，我认为使用哈希表是合理的选择。