[LeetCode]3Sum

这道题可以reduce成2sum的问题，我们遍历[0, N)的元素，每次锁定第一个元素，之后右边的subarray就会变成two sum问题。2sum有两种解法，写代码的时候要注意去重。

HashMap解法:
主要是去重的部分，sort输入array。如果第一个元素之前visit过了，我们直接跳过。对于2sum的部分，我们不能简单的check上一个元素是不是和当前元素相同然后跳过，这样的话我们会漏掉一些情况，比如输入为(0, 0, 0)我们就找不到和为0的一对pair。所以我们需要把去重的部分放在找到符合条件的pair的时候，一旦找到了我们就跳过之后所有重复的元素。时间复杂度为O(N^2)，空间O(N)。代码如下：

Two pointer解法：
同样要sort，和HashMap的去重方法是类似的，一旦我们找打了和为target的一对pair，两个指针一直移动跳过所有的重复元素。时间复杂度为O(N^2)，常数空间。代码如下: