Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
def threeSum(self, nums):
nums.sort()
r = []
for i in range(0, len(nums)):
a, b = 0, len(nums)-1
while True:
a = a if a != i else a + 1
b = b if b != i else b - 1
if a >= b:
break
if nums[a] + nums[b] == -nums[i]:
t = [nums[i], nums[a], nums[b]]
flag = True
for z in r:
if set(t) == set(z):
flag = False
break
if flag:
r.append(t)
b -= 1
a += 1
elif nums[a] + nums[b] > -nums[i]:
b -= 1
else:
a += 1
return r