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;
}
Copy The Code & Try With Live Editor

Input

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

Output

x
+
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 & Try With Live Editor

Input

x
+
cmd
nums = [0,1,1]

Output

x
+
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++) {
      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);
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,0,0]

Output

x
+
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 & Try With Live Editor

Input

x
+
cmd
nums = [0,0,0]

Output

x
+
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]])
                    res_set.add((nums[i], nums[l], nums[r])) 
                else: l, r = l + 1, r - 1
        return res
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1,1]

Output

x
+
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 & Try With Live Editor

Input

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

Output

x
+
cmd
[[-1,-1,2],[-1,0,1]]
Advertisements

Demonstration


Previous
#14 Leetcode Longest Common Prefix Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#16 Leetcode 3Sum Closest Solution in C, C++, Java, JavaScript, Python, C# Leetcode