Problem

Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+b+c= 0? Find all unique triplets in the array which gives the sum of zero.
Leetcode 3sum

Think

[a,b,c] 独一性是这个问题中比较难以解决的问题，使用列表哈希可以解决这个问题。假设[a,b,c]是按照从小到大的顺序排列的,则hash_val = str(a) + str(b) + str(c)
每一次在找到三个数相加为0 的时候都应该按照从小到大的顺序去计算哈希值，如果hash_set中没有计算出的哈希值，就认为a,b,c这个列表值没有出现过，我们就把,a,b,c当做答案最后的结果之一记录下来，然后把此次计算的哈希值推入到hash_set当中去。
但hash函数的选择非常重要，直接利用字符串相加的方法会超时，不合适的计算方法有可能导致在数据量特别大的时候造成两个不同的列表计算出来的hash值却是一样的。最终通过的hash计算方法是：
hash_val = 10000 * a + b（只需要两个值就可以了，因为a + b + c = 0，两个值就可以确定第三个值了）种方法计算的结果在时间上的表现确实不是十分理想。

def threeSum(self, nums):
      size = len(nums)
      li = sorted(nums)
      ans = []
      neg = collections.defaultdict(int)
      neg_li = []
      pos = collections.defaultdict(int)
      pos_li = []
      hash_set = set()
      zeros = 0
      for item in li:
          if item < 0:
              neg_li.append(item)
              neg[item] += 1
          elif item > 0:
              pos_li.append(item)
              pos[item] += 1
          else:
              zeros += 1
      if zeros > 0:
          for ele in pos:
              if (0 - ele) in neg:
                  ans.append([(0 - ele), 0, ele])
      if zeros >= 3:
          ans.append([0, 0, 0])
      for i in range(len(neg_li) - 1):
          a = neg_li[i]
          for j in range(i+1, len(neg_li)):
              b = neg_li[j]
              c = 0 - a - b
              hash_val = a * -10000 + b*(-100)
              if pos[c] > 0 and hash_val not in hash_set:
                  ans.append([a, b, c])
                  hash_set.add(hash_val)
      hash_set.clear()
      for i in range(len(pos_li) - 1):
          a = pos_li[i]
          for j in range(i+1, len(pos_li)):
              b = pos_li[j]
              c = 0 - a - b
              hash_val = b * 10000 + a * 100
              if neg[c] > 0 and hash_val not in hash_set:
                  ans.append([c, a, b])
                  hash_set.add(hash_val)
      return ans

这是一段值得优化的代码不仅代码显得非常冗余，而且运行的速度也不是非常理想。代码的复杂度是O(N * N)