Given an array`nums`

ofnintegers, are there elementsa,b,cin`nums`

such thata+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.Example:Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

This is extended from [Leetcode]1. Two Sum – if we fix one number `nums[i]`

at a time, then it’s a Two Sum now: to find two numbers `a`

and `b`

such that `a+b=nums[i]`

.

#### Logic 1 – Two pointers

Since it asks for the number but not index, we can **sort the array first** and apply two pointers: to find two numbers `a`

and `b`

such that `a+b=nums[i]`

, we use two pointers `left=i+1`

(instead of `0`

to avoid repetition) and `right=len(nums)-1`

; if `nums[a]+nums[b]<nums[i]`

, we move `left`

to the right; if `nums[a]+nums[b]>nums[i]`

, we move `right`

towards the left.

Python:

```
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ret = []
for i in range(n-2):
# nums[i]>0 means nums[l] and nums[r]
# will be larger than 0. Not possible.
if nums[i] > 0:
break
# to avoid repetition
if i > 0 and nums[i] == nums[i-1]:
continue
l,r = i+1,n-1
while l<r:
total = nums[i] + nums[l] + nums[r]
if total < 0:
l+=1
elif total > 0:
r -= 1
else:
ret.append([nums[i], nums[l], nums[r]])
# to avoid repetition
while l < r and nums[l]==nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return ret
```

#### Logic 2 – Binary search

Logic 1 achieves O(n^2) and it performs well in C++ and Java: it beats >90\%. However, in Python, it only beats <30\%. Therefore I looked into some of the fast submissions and found the following solution. I cannot track the author so I have nowhere to refer to, yet I’d like to declare that the following solution is borrowed from Leetcode.

Generally speaking, it also selects one element `num`

at a time and search for the other two `a`

and `b`

if they exist. What’s different is that, instead of applying two-pointer to check the subarray, it stores the `collections.Counter`

of the array first, then uses binary search to set a search range, and search through that range.

- With using
`counter`

, it needs to handle different cases separately to avoid redundancy:

case i. three numbers are the same – the only possible solution is`[0,0,0]`

case ii. two numbers are the same – needs to check against`counter`

to ensure`counter[num] > 1 and -2 * num in counter`

case iii. all of them are different `bisect_left`

the leftmost boundary for searching would be the smallest element to the right of`i+1`

, that’s why the value is set to`opposite - nums[-1]`

`bisect_right`

we choose`opposite / 2`

over`opposite-nums[left]`

to deal with repeated solutions.

For example, given`[-1,0,1]`

, and`num=-1`

, we only wish to search`[0]`

to get`[-1,0,1]`

, instead of searching`[0,1]`

which leads to`[-1,0,1],[-1,1,0]`

```
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
counter = collections.Counter(nums)
nums = sorted(counter)
ret = []
for i, num in enumerate(nums):
# case i. three numbers are the same - [0,0,0]
if num==0:
if counter[num] > 2:
ret.append([0, 0, 0])
# case ii. two numbers are the same
elif counter[num] > 1 and -2 * num in counter:
ret.append([num, num, -2 * num])
# case iii. not any of the three numbers are the same
if num < 0:
opposite = -num
left = bisect_left(nums, opposite - nums[-1], i + 1)
right = bisect_right(nums, opposite / 2, left)
for a in nums[left:right]:
b = opposite - a
if b in counter and a!=b:
ret.append([num, a, b])
return ret
```