Two Sum算法的小trick（Leetcode的premium的解答没有讲到的)

最开始其实想说一下Leedcode提供的实现的代码质量其实真的一般，如果有人面试的时候用实例代码的风格，我估计算法写的再好也没太大用。最简单的变量命名。尽然有这样的代码:

Map<Integer, Integer> map = new HashMap<>();

每定义一个变量都要花时间至少稍微想一个变量命名，这是一个最基本的习惯。写出用map作为变量名的人绝对不是有经验的好工程师应该做的事情。

好了，言归正传。

Two Sum可以算是算法题里面最简单的之一了。下面是题目和LeetCode Premium给出的一个SolutionO(N) Solution.

题目:
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order.

下面是采用Two Pass的 O(N)时间复杂度的解答:

To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.
We can reduce the lookup time from O(n) to O(1) by trading space for speed. A hash table is well suited for this purpose because it supports fast lookup in near constant time. I say “near” because if a collision occurred, a lookup could degenerate to O(n) time. However, lookup in a hash table should be amortized O(1) time as long as the hash function was chosen carefully.

class Solution
{
    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) };
            }
        }
        // In case there is no solution, we’ll just return null
        return null;
    }
}

LeetCode里面没有说的是第一个loop可能存在两个未知的数字相同的情况。这样loop结束以后map里面的value就是最后出现那个数字的位置。比如说[1,2,3,2]，map里面是[2,3] 而不是[2,1]。 但是这个解答依然是对的是因为第二个循环一定是从小到大循环的，这样就不会出现重复使用同一个位置的数字的情况。但是如果把第二个循环倒序的话，算法就错了。
可能有人会问如果是【1，2，2，2，3】，同一个数字出现三个怎么办？其实题目是要求是可以假定结果只有唯一解，如果有三个的话就可能会有多个解了。算法终归是算法，two sum的题目本身简化了很多东西，所以这种hash的算法在真实场景中，没有那些限定条件的话，还是会有bug的。

顺便附上One Pass吧。One Pass其实没啥区别，反倒不如two pass直观。

class Solution
{
public int[] twoSum(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target – nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
// In case there is no solution, we’ll just return null
return null;
}
}