```
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
if not num:
return []
hash_table = {}
for i in range(len(num)):
if num[i] not in hash_table:
hash_table[num[i]] = 1
else:
hash_table[num[i]] += 1
res = []
for i in range(len(num)):
for j in range(i+1,len(num)):
hash_table[num[i]] -= 1
hash_table[num[j]] -= 1
wanted = -num[i]-num[j]
if wanted in hash_table and hash_table[wanted] > 0:
new = [num[i],num[j], wanted]
new.sort()
if new not in res:
res.append(new)
hash_table[num[i]] += 1
hash_table[num[j]] += 1
return res
```