Skip to main content

3Sum

Problem

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]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

 

Constraints:

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

Solution

/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const res = [];
nums.sort((a, b) => a - b);

for (let i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
// skip duplicate starting values
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}

// modified sorted two sum solution
const sum = -nums[i];
let lo = i + 1;
let hi = nums.length - 1;

while (lo < hi) {
const val = nums[lo] + nums[hi];
if (val > sum) {
hi--;
} else if (val < sum) {
lo++;
} else {
// three sum found
res.push([nums[i], nums[lo], nums[hi]])

do { // skip duplicate nums[hi] values
hi--;
} while (lo < hi && nums[hi] === nums[hi + 1])

do { // skip duplicate nums[lo] values
lo++;
} while (lo < hi && nums[lo] === nums[lo - 1])
}
}
}
return res;
};

This problem reduces down to the Two Sum II - Input array is sorted problem. More specifically, if we can find two values nums[i] and nums[j] from nums that sums up to -nums[k] from nums, then we have found a triplet such that nums[i] + nums[j] + nums[k] = 0. That said, since this problem asks for all unique and valid triplets, we must skip duplicate values throughout the process to ensure res contains no duplicates (this can be done by sorting nums).

Notice that the condition for our loop to terminate is i < nums.length - 2 && nums[i] <= 0. More specifically, for the first condition, if there are only two elements left, we can't form a triplet; for the second condition, since nums is sorted, once nums[i] > 0, all remaining elements are positive (ie. it is not possible for three positive values to add up to 0).