"""

This is the answer from @caikehe and all the comments below

The main idea is to iterate every number in nums.

We use the number as a target to find two other numbers which make total zero.

For those two other numbers, we move pointers, `l` and `r`, to try them.

`l` start from left to right.

`r` start from right to left.

First, we sort the array, so we can easily move i around and know how to adjust l and r.

If the number is the same as the number before, we have used it as target already, continue. [1]

We always start the left pointer from `i+1` because the combination of 0~`i` has already been tried. [2]

Now we calculate the total:

If the total is less than zero, we need it to be larger, so we move the left pointer. [3]

If the total is greater than zero, we need it to be smaller, so we move the right pointer. [4]

If the total is zero, bingo! [5]

We need to move the left and right pointers to the next different numbers, so we do not get repeating result. [6]

We do not need to consider `i` after `nums[i]>0`, since sum of 3 positive will be always greater than zero. [7]

We do not need to try the last two, since there are no rooms for `l` and `r` pointers.

You can think of it as The last two have been tried by all others. [8]

For time complexity

Sorting takes `O(NlogN)`

Now, we need to think as if the `nums` is really really big

We iterate through the `nums` once, and each time we iterate the whole array again by a while loop

So it is `O(NlogN+N^2)~=O(N^2)`

For space complexity

We didn't use extra space except the `res`

Since we may store the whole 'nums' in it

So it is `O(N)`

`N` is the length of `nums`

"""

class Solution(object):

def threeSum(self, nums):

res = []

nums.sort()

length = len(nums)

for i in xrange(length-2): #[8]

if nums[i]>0: break #[7]

if i>0 and nums[i]==nums[i-1]: continue #[1]

l, r = i+1, length-1 #[2]

while l<r:

total = nums[i]+nums[l]+nums[r]

if total<0: #[3]

l+=1

elif total>0: #[4]

r-=1

else: #[5]

res.append([nums[i], nums[l], nums[r]])

while l<r and nums[l]==nums[l+1]: #[6]

l+=1

while l<r and nums[r]==nums[r-1]: #[6]

r-=1

l+=1

r-=1

return res

"""

def threeSum(self, nums):

def twoSum(target, nums):

res = []

seen = collections.Counter()

for n1 in nums:

n2 = target-n1

if n1 in seen or n2 in seen or n2 not in nums: continue

if n1==n2 and nums[n1]<2: continue

seen[n1]+=1

seen[n2]+=1

res.append([target*-1, n1, n2])

return res

res = []

zero = 0

positive = collections.Counter()

negative = collections.Counter()

for n in nums:

if n>0:

positive[n]+=1

elif n==0:

zero+=1

else:

negative[n]+=1

if zero>=3:

res.append([0, 0, 0])

if zero>=1:

for p in positive:

if p*-1 in negative:

res.append([0, p, p*-1])

for p in positive:

res+=twoSum(p*-1, negative)

for n in negative:

res+=twoSum(n*-1, positive)

return res

"""