### Question

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:**

- Elements in a triplet (
*a*,*b*,*c*) must be in non-descending order. (ie,*a*≤*b*≤*c*) - 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)

### Stats

Frequency | 5 |

Diffficulty | 3 |

Adjusted Difficulty | 5 |

Time to use | ---------- |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

First of all, the array must be sorted first.

**This question is solved with O(n ^{2}) time**. The idea is, for every integer, try to find a 2-integer pair so that the 3 numbers sum to 0. The method to use is

**2-pointer scan**.

### Solution

**Very important point of this question**: there might be duplications in the result.

Eg. array = {-5, 2, 2, 3, 3}. When a = -5, we can choose 2, 3 and move pointers both by 1 position. Then we can choose 2, 3 again!

Solution is to increase the pointer to where the value is different. Pay special attention in writing the code. Because there are 3 parts that need duplication avoidance:

**The pivot number that we select, must be distinct each time**. Why? because this is the smallest of the triplet. It must not be same.The left pointer and right pointer. They should point to a new value each time.

Note that when sum is too large, move left pointer, and vice versa.

**However when sum is == 0, we move both left and right pointer**.

Point 3 is the reason why we have 2 conditions in seperate if-block:

```
if (sum >= 0) {...}
if (sum <= 0) {...}
```

### My code

```
public class Solution {
public List<List<Integer>> threeSum(int[] num) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if (num == null || num.length < 3) {
return ans;
}
Arrays.sort(num);
int len = num.length;
int left, right;
for (int i = 0; i < len; i++) {
// duplication avoidance 1
if (i != 0 && num[i] == num[i - 1]) {
continue;
}
left = i + 1;
right = len - 1;
while (left < right) {
int sum = num[i] + num[left] + num[right];
if (sum == 0) {
// now one triplet is found, add it to ans list
List<Integer> triplet = new ArrayList<Integer>();
triplet.add(num[i]);
triplet.add(num[left]);
triplet.add(num[right]);
ans.add(triplet);
}
// shrink the range between left and right pointer
// (until the 2 pointers met)
if (sum >= 0) {
// move right pointer to the left
right--;
// duplication avoidance 2
while (right >= 0 && num[right] == num[right + 1]) {
right--;
}
}
if (sum <= 0) {
// move left pointer to the right
left++;
// duplication avoidance 3
while (left < len && num[left] == num[left - 1]) {
left++;
}
}
}
}
return ans;
}
}
```