Algorithm
Problem Name: 15. 3Sum
Problem Link: https://leetcode.com/problems/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
add2res(&res, nums[i], nums[x], nums[y]);
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;
}
Input
nums = [-1,0,1,2,-1,-4]
Output
[[-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;
}
};
Input
nums = [0,1,1]
Output
[]
#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++) {
if (duplicates.add(nums[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);
result.add(temp);
}
map.put(nums[j], i);
}
}
}
return new ArrayList < >(result);
}
}
Input
nums = [0,0,0]
Output
[[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
}
Input
nums = [0,0,0]
Output
[[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]])
res_set.add((nums[i], nums[l], nums[r]))
else: l, r = l + 1, r - 1
return res
Input
nums = [0,1,1]
Output
[]
#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);
}
}
}
Input
nums = [-1,0,1,2,-1,-4]
Output
[[-1,-1,2],[-1,0,1]]