## Algorithm

Problem Name: 15. 3Sum

Given an integer array nums, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`.

Notice that the solution set must not contain duplicate triplets.

Example 1:

```Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
```

Example 2:

```Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
```

Example 3:

```Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
```

Constraints:

• `3 <= nums.length <= 3000`
• `-105 <= nums[i] <= 105`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct res_s {
int **p;
int sz;
int n;
} res_t;
void add2res(res_t *res, int a, int b, int c) {
int *buff = malloc(3 * sizeof(int));
//assert(buff);
buff[0] = a;
buff[1] = b;
buff[2] = c;

if (res->sz == 0) {
res->sz = 10;
res->p = malloc(res->sz * sizeof(int **));
//assert(res->p);
} else if (res->sz == res->n) {
res->sz *= 2;
res->p = realloc(res->p, res->sz * sizeof(int **));
//assert(res->p);
}
res->p[res->n ++] = buff;
}
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int** threeSum(int* nums, int numsSize, int* returnSize) {
int i, x, y, k;
res_t res = { 0 };

qsort(nums, numsSize, sizeof(int), cmp);

for (i = 0; i  <  numsSize - 2; i ++) {
if (i != 0 && nums[i] == nums[i - 1]) continue;
x = i + 1;
y = numsSize - 1;
while (x  <  y) {
k = nums[i] + nums[x] + nums[y];
if (k == 0) {
// found one
x ++;
while (x  <  y && nums[x] == nums[x - 1]) x ++;
y --;
while (x  <  y && nums[y] == nums[y + 1]) y --;
} else if (k < 0) {
x ++;
while (x  <  y && nums[x] == nums[x - 1]) x ++;
} else {
y --;
while (x  <  y && nums[y] == nums[y + 1]) y --;
}
}
}

*returnSize = res.n;
return res.p;
}
``````
Copy The Code &

Input

cmd
nums = [-1,0,1,2,-1,-4]

Output

cmd
[[-1,-1,2],[-1,0,1]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector < vector<int>>res;
sort(nums.begin(), nums.end());
for(int i = 0; i  <  (int)nums.size() - 1; i++){
if(i > 0 && nums[i - 1] == nums[i]) continue;
int lo = i + 1;
for(int hi = nums.size() - 1; hi > lo; hi--){
if(hi < nums.size() - 1 && nums[hi] == nums[hi + 1]) continue;
while(nums[lo]  <  -(nums[i] + nums[hi])) lo++;
if(lo < hi && (nums[i] + nums[lo] + nums[hi]) == 0) res.push_back({nums[i], nums[lo], nums[hi]}>;
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
nums = [0,1,1]

Output

cmd
[]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List();
Set duplicates = new HashSet<>();
Map < Integer, Integer> map = new HashMap<>();
for (int i = 0; i  <  nums.length; i++) {
for (int j = i + 1; j  <  nums.length; j++) {
int target = -nums[i] - nums[j];
if (map.containsKey(target) && map.get(target) == i) {
List < Integer> temp = Arrays.asList(nums[i], nums[j], target);
Collections.sort(temp);
}
map.put(nums[j], i);
}
}
}
return new ArrayList < >(result);
}
}
``````
Copy The Code &

Input

cmd
nums = [0,0,0]

Output

cmd
[[0,0,0]]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const threeSum = function (nums) {
nums.sort((a, b) => a - b)
const res = []
let lo, hi, sum
for (let i = 0; i  <  nums.length - 2; i++) {
if (nums[i] > 0) break
if (nums[i] === nums[i - 1]) continue
if (i === 0 || (i > 0 && nums[i] !== nums[i - 1])) {
lo = i + 1
hi = nums.length - 1
sum = 0 - nums[i]
while (lo < hi) {
if (nums[lo] + nums[hi] === sum) {
res.push([nums[i], nums[lo], nums[hi]])
while (lo < hi && nums[lo] === nums[lo + 1]) lo += 1
while (lo < hi && nums[hi] === nums[hi - 1]) hi -= 1
lo += 1
hi -= 1
} else if (nums[lo] + nums[hi] < sum) lo++
else hi--
}
}
}
return res
}
``````
Copy The Code &

Input

cmd
nums = [0,0,0]

Output

cmd
[[0,0,0]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def threeSum(self, nums):
res, res_set = [], set()
nums.sort()
for i in range(len(nums) - 2):
l, r = i + 1, len(nums) - 1
while l < r:
sm = nums[i] + nums[l] + nums[r]
if sm < 0: l += 1
elif sm > 0: r -= 1
elif (nums[i], nums[l], nums[r]) not in res_set:
res.append([nums[i], nums[l], nums[r]])
else: l, r = l + 1, r - 1
return res
``````
Copy The Code &

Input

cmd
nums = [0,1,1]

Output

cmd
[]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _015_3Sum
{
public IList < IList<int>> ThreeSum(int[] nums)
{
var results = new List < IList<int>>();
if (nums.Length  <  3) return results;

Suffle(nums);
Quick3WaySort(nums, 0, nums.Length - 1);

if (nums[0] > 0) return results;
if (nums[nums.Length - 1]  <  0) return results;

for (int i = 0; i  <  nums.Length - 2 && nums[i] <= 0; i++)
{
int lo = i + 1, hi = nums.Length - 1;
while (lo  <  hi && nums[hi] >= 0)
{
var sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0)
do
lo++;
while (lo  <  hi && nums[lo - 1] == nums[lo]);
else if (sum > 0)
do
hi--;
while (lo  <  hi && nums[hi] == nums[hi + 1]);
else
{
results.Add(new List<int>() { nums[i], nums[lo], nums[hi] });
do
lo++;
while (lo  <  hi && nums[lo - 1] == nums[lo]);
do
hi--;
while (lo  <  hi && nums[hi] == nums[hi + 1]);
}
}

while (i < nums.Length - 2 && nums[i] == nums[i + 1])
i++;
}
return results;
}

void Suffle(int[] nums)
{
var random = new Random();
int N = nums.Length;
int r, temp;
for (int i = 0; i  <  N; i++)
{
r = random.Next(i + 1);

temp = nums[r];
nums[r] = nums[i];
nums[i] = temp;
}
}

void Quick3WaySort(int[] nums, int lo, int hi)
{
if (lo >= hi) { return; }
var lt = lo;
var gt = hi;
var i = lo;
var v = nums[i];
int temp;

while (i  < = gt)
{
if (nums[i] > v)
{
temp = nums[i];
nums[i] = nums[gt];
nums[gt--] = temp;
}
else if (nums[i]  <  v)
{
temp = nums[i];
nums[i] = nums[lt];
nums[lt++] = temp;
}
else { i++; }
}
Quick3WaySort(nums, lo, lt - 1);
Quick3WaySort(nums, gt + 1, hi);
}
}
}
``````
Copy The Code &

Input

cmd
nums = [-1,0,1,2,-1,-4]

Output

cmd
[[-1,-1,2],[-1,0,1]]