三数之和

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

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

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

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

解题思路：
最简单的思路：直接三个循环嵌套，后两个循环从上一个索引开始到数组结尾遍历，然后求和看等不等于0。但这样耗时较多，虽然能达到题目的要求，但也要排到很后面了。
然后是下面这种，排在最前面的大佬的思路。
先用字典统计出现的数字及他们的个数
比如上面的例子就变成了
{-1:2, 0:1, 1:1 ...}这种了
然后再把字典的键分为正数和负数两个列表
分别在两个列表中取数，用0减去这两个数，获得第三个数
再到字典的键中查找有没有这个数
有这个数的话，还要考虑两种情况
第三个数是否和前两个数相同，如例子中的两个-1
如果相同的话，那原数组中就必须有两个才行
比如例子中有 -4和2，那么0-(-4)-2=2
但原数组中只有一个2，所以[-4,2,2]是不能作为结果的
还有一种是三个数都不相同，那么自然就是结果之一了
因为前面已经用字典把重复的数字合并了，所以结果中也不会出现重复的情况。

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        return_list = []
        a = {}
        for i in nums:
            a[i] = a.get(i, 0) + 1
        if 0 in a and a[0] >= 3:
            return_list.append([0, 0, 0])
            
        neg = [i for i in a if i < 0]
        pos = [i for i in a if i >= 0]
        
        for i in neg:
            for j in pos:
                dif = 0 - i - j
                if dif in a:
                    if dif in [i, j] and a[dif] >= 2:
                        return_list.append([i, j, dif])
                    if i < dif < j:
                        return_list.append([i, j, dif])
        
        return return_list