三数之和

https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1020/

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

本题可以借鉴两个数之和的思路，其实三个数的和等于0，其实就是找a+b=-c
最简单的方法是遍历3次，看是否满足等式，但是显然不能满足LeetCode时间复杂度要求

进一步地，可以用hash表的思想，先把数组中每个数字出现次数统计出来，然后给定ab后，只要判断-c在不在数组中即可，相当于降低了复杂度，变为O（n2）。但是你还可以更优秀！

比较好的思路是，考虑到结果需要去重，我们可以假定满足条件的元素为abc，a+b+c=0，且a<=b<=c。于是我们可以遍历a和c，再中间找到b就可以。一般来说，a都会小于0，c都会大于等于0，才能满足a+b+c=0。那么具体思路如下：

1. 对数组每个元素统计出现次数，放入hash表中，同时将数组中大于等于0的数放在pos中，小于0放在neg中
2. 特殊情况处理：对于有3个0的，直接append结果中
3. 遍历pos和neg，相当于先定位了a和c，计算b=0-a-c，如果b在hash表中，则表明肯定能成。但是为了去重，需要考虑2中情况
   1. a==b or c==b，这时候判断对应的c在hash表中出现的次数是否大于等于2,满足则把结果append
   2. 这里是为了去重，所以限制了a<b<c（等于的情况在1中考虑了），满足这个条件的才能append到结果中

这样的话，算法复杂度为O(k*m) + O(n)，其中k+m = n

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        num_hash = {}
        pos_arr = []
        neg_arr = []
        for each_num in nums:
            num_hash[each_num] = num_hash.get(each_num,0) + 1
            if each_num>=0 and each_num not in pos_arr:
                pos_arr.append(each_num)
            if each_num<0 and each_num not in neg_arr:
                neg_arr.append(each_num)
        if 0 in num_hash and num_hash[0]>=3:
            result.append([0,0,0])
        for i in pos_arr:
            for j in neg_arr:
                diff = 0 - i - j
                if diff in num_hash:
                    print diff,i,j
                    if diff == i or diff == j:
                        if num_hash[diff] >= 2:
                            result.append([i,j,diff])
                    elif j<diff<i:
                        result.append([i,diff,j])
        return result