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

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);
        }
        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的。[/i]
[i]附上one pass吧：[/i]
[i]class Solution {[/i]
[i]    public int[] twoSum(int[] nums, int target) {[/i]
[i]        Map<Integer, Integer> map = new HashMap<>();[/i]
[i]        for (int i = 0; i < nums.length; i++) {[/i]
[i]            int complement = target - nums[i];[/i]
[i]            if (map.containsKey(complement)) {[/i]
[i]                return new int[] { map.get(complement), i };[/i]
[i]            }[/i]
[i]            map.put(nums[i], i);[/i]
[i]        }[/i]
[i]        // In case there is no solution, we'll just return null[/i]
[i]        return null;[/i]
[i]    }[/i]
[i]}


[/i]