Skip to content

[LeetCode] 15. 3Sum

Published: at 10:07 AM (4 min read)

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:

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

nums[i]+nums[j]+nums[k]=0nums[i]+nums[j]=nums[k]nums[i] + nums[j] + nums[k] = 0 \quad \Longrightarrow \quad nums[i] + nums[j] = -nums[k]

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 (numI=numJnumKnumI = -numJ - numK), 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 O(n2)O(n^2), where nn is the number of elements in the input array. The outer loop runs nn times, and the inner loop runs n1n-1 times. The inner loop runs n1n-1 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 O(n)O(n). 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 O(n)O(n) space. Combined, total space complexity of O(n)O(n).


Previous Post
[Firefox] drag 事件 client/page 與 offset 等座標位置不正常運作
Next Post
[GitHub] 如何將 public repo 調整成 private repo