LeetCode 15. 3Sum (javascript)

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

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⁵ <= nums[i] <= 10⁵

Idea:

Sort nums + two pointers
Enumerate nums[i]
Use two pointers to find all possible sets of (i, l, r) such that
- i < l < r
- nums[i] + nums[l] + nums[r] === 0
How to move pointers?
- nums[i] + nums[l] + nums[r] > 0, too large, decrease r
- nums[i] + nums[l] + nums[r] > 0, too small, increase l

Optimize:

skip: if nums[i] > 0, then nums[i] + nums[l] + nums[r] never = 0
skip same number: nums[i] === nums[i – 1]

Solution:

Time complexity: O(nlogn + n^2)

Space complexity: O(1)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const n = nums.length;
    let res = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < n - 2; i++) {
        // skip: if nums[i] > 0,
        // then nums[i] + nums[l] + nums[r] never = 0
        if (nums[i] > 0) break; 
        // skip same number
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let l = i + 1;
        let r = n - 1;
        while (l < r) {
            if (nums[i] + nums[l] + nums[r] === 0) {
                res.push([nums[i], nums[l++], nums[r--]]);
                // skip same number
                while (l < r && nums[l] === nums[l - 1]) l++;
                while (l < r && nums[r] === nums[r + 1]) r--;
            } else if (nums[i] + nums[l] + nums[r] > 0) {
                r--;
            } else {          
                l++;
            }  
        }
    }
    return res;
};