Published on

[LeetCode 15] 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

Thoughts

  • We have integer array, we check for sum, maybe sort first?
  • For sorted array, we can move to mid

Typescript

function threeSum(nums: number[]): number[][] {
    const res = []
    // notice how we sort the array here
    nums.sort((a, b) => a - b)

    // we use i as the first element in result
    for(let i = 0; i < nums.length - 2; i++) {
        // we dont need any duplicate first elements
        if(i > 0 && nums[i] === nums[i - 1]) continue;

        // set index for second & last element
        let l = i + 1, r = nums.length - 1;

        // move to mid
        while(l < r) {
            const sum = nums[i] + nums[l] + nums[r]

            if(sum > 0){
                r--;
            } else if (sum < 0) {
                l++;
            } else {
                res.push([nums[i], nums[l], nums[r]])
                l++
                while (nums[l] === nums[l - 1] && l < r) l++;
            }
        }
    }

    return res;
};

Reference