Table of Contents
Open Table of Contents
Description
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 sum up to 0
.
Approach
Refer to the solution for [Leetcode] 1. Two Sum and reinterpret the equation
This transforms the problem into finding two numbers whose sum equals a target value.We can use a similar approach to find the two numbers that sum to -nums[k].
We’ll iterate through the sorted array, considering each element as a candidate for the second element (numJ
). For each numJ
, we loop through the subsequent elements as potential third elements (numK
), calculate the required first element (), and then check if that numI
was encountered earlier. If so, the triplet is valid.
Solution
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
// Minimum number of elements required to form a triplet
const MIN_COUNT = 3;
// Early return scenarios:
// 1. If there are fewer than 3 numbers.
// 2. If all numbers are positive (then no three numbers can sum to zero).
if (nums.length < MIN_COUNT || nums.every(num => num > 0)) return [];
if (nums.every(num => num === 0)) return [[0, 0, 0]];
// Sorting facilitates the process of avoiding duplicate triplets.
const sortedNums = nums.sort((a, b) => a - b);
// Map to track numbers that have been seen so far.
const potentialNumIMap = {};
// Object to store unique triplets.
const tripletMap = {};
// Iterate over each element considering it as the second element (numJ) in the triplet.
for (let j = 0; j < sortedNums.length; j++) {
const numJ = sortedNums[j];
// For each numJ, iterate over the subsequent elements to consider as the third element (numK) in the triplet.
for (let k = j + 1; k < sortedNums.length; k++) {
const numK = sortedNums[k],
// Calculate the required first element (numI) so that the sum of the triplet equals zero.
numI = -numJ - numK;
const triplet = [numI, numJ, numK];
// If the required numI was already seen, this forms a valid triplet.
if (potentialNumIMap[numI]) {
// Using the triplet as a key string helps avoid adding duplicates.
tripletMap[triplet] = triplet;
}
}
// Mark numJ as seen, making it available as a potential numI for future pairs.
potentialNumIMap[numJ] = true;
}
return Object.values(tripletMap);
};
Complexity Analysis
Time Complexity
The time complexity is , where is the number of elements in the input array. The outer loop runs times, and the inner loop runs times. The inner loop runs times because the outer loop iterates through the array, and the inner loop iterates through the remaining elements.
Space Complexity
The overall space complexity is . We use a map to record each number encountered, which in the worst case may store up to n
elements. Additionally, we store unique triplets in an object. Even though each triplet contains three numbers, at most n/3
triplets will be recorded, still contributing space. Combined, total space complexity of .