15. 3Sum

Problem

Tags: Array, Two Pointers, Sorting

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
• -10^5 <= nums[i] <= 10^5

Code

JS

// 15. 3Sum (10/6/53764)
// Runtime: 136 ms (85.93%) Memory: 49.30 MB (94.83%) 

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

    const results = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let ptrL = i + 1,
            ptrR = nums.length - 1;
        while (ptrL < ptrR) {
            const sum = nums[i] + nums[ptrL] + nums[ptrR];
            if (sum === 0) {
                results.push([nums[i], nums[ptrL++], nums[ptrR--]]);
                while (ptrL < ptrR && nums[ptrL] === nums[ptrL - 1]) ptrL++;
                while (ptrL < ptrR && nums[ptrR] === nums[ptrR + 1]) ptrR--;
            } else if (sum < 0) ptrL++;
            else ptrR--;
        }
    }

    return results;
}