15. 3Sum

Problem

https://leetcode.com/problems/3sum/

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

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

Solution1

Pick a unique number as the first element, then use Two Sum method to figure out the rest.

1. Sort the array.
2. Loop the left half sortedNums[i] <= 0 to pick the first number, skip the duplicate ones.
3. Now we have target = -sortedNums[i], calculate the two sum from i+1 to sortedNums.length.
4. When a value in the map is used, dump it by setting false.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let sortedNums = nums.sort((a, b) => { return a - b })
    sortedNums.unshift(null)

    let results = []
    for (let i = 1; i < sortedNums.length && sortedNums[i] <= 0; i += 1) {
        if (sortedNums[i] !== sortedNums[i-1]) {
            let r = [sortedNums[i]]
            let target = -sortedNums[i]
            let dict = {}

            for (let j = i+1; j < sortedNums.length; j += 1) {
                let diff = target-sortedNums[j]
                if (dict[diff]) {
                    results.push(r.concat([diff, sortedNums[j]]))
                    dict[diff] = false
                }

                if (typeof dict[sortedNums[j]] === 'undefined') {
                    dict[sortedNums[j]] = true
                }
            }
        }
    }
    return results
};

Solution2

Solution2 is faster and more comprehensible but a bit longer.

It basically breaks the problem into 4 parts:

1. [0, 0, 0]
2. [0, +, -]
3. [+, +, -]
4. [-, +, -]

For example, if we have taken a positive number as the first element, now all we have to do is to loop the rest of the positive numbers that are greater than the picked one, and check if any corresponding negative number exists(by map).

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    if (!Array.isArray(nums) || nums.length < 3) {
        return []
    }

    let sortedNums = nums.sort((a, b) => { return a - b })

    let posStart, posEnd
    let zerStart, zerEnd
    let negStart, negEnd
    let results = []

    let i = 0
    if (sortedNums[i] < 0) {
        negStart = i
        while (i < sortedNums.length && sortedNums[i] < 0) {
            i += 1
        }
        negEnd = i - 1
        // All negative
        if (i === sortedNums.length) {
            return []
        }
    }
    if (sortedNums[i] === 0) {
        zerStart = i
        while (i < sortedNums.length && sortedNums[i] === 0) {
            i += 1
        }
        zerEnd = i - 1
        if (i - zerStart >= 3) {
            results.push([0, 0, 0])
        }
        // All negative & zero
        if (i === sortedNums.length) {
             return results
        }
    }
    posStart = i
    posEnd = sortedNums.length - 1

    let negDict = {}
    let posDict = {}
    for (let i = negStart; i <= negEnd; i += 1) {
        negDict[sortedNums[i]] = true
    }
    for (let i = posStart; i <= posEnd; i += 1) {
        posDict[sortedNums[i]] = true
    }

    // [0, -, +]
    if (zerStart <= zerEnd) {
        let r = [0]
        for (let i = negStart; i <= negEnd; i += 1) {
            // unique
            if (sortedNums[i] !== sortedNums[i+1]) {
                let target = -sortedNums[i]
                if (posDict[target]) {
                    results.push(r.concat([target, -target]))
                }
            }
        }
    }

    // [-, -, +]
    for (let i = negStart; i <= negEnd; i += 1) {
        // unique
        if (sortedNums[i] !== sortedNums[i-1]) {
            let r = [sortedNums[i]]
            let target = -sortedNums[i]
            for (let j = i+1; j <= negEnd; j += 1) {
                // unique
                if (sortedNums[j] !== sortedNums[j+1] &&
                        posDict[target-sortedNums[j]]) {
                    results.push(r.concat([sortedNums[j], target-sortedNums[j]]))
                }
            }
        }
    }

    // [+, +, -]
    for (let i = posStart; i <= posEnd; i += 1) {
        // unique
        if (sortedNums[i] !== sortedNums[i-1]) {
            let r = [sortedNums[i]]
            let target = -sortedNums[i]
            for (let j = i+1; j <= posEnd; j += 1) {
                // unique
                if (sortedNums[j] !== sortedNums[j+1] &&
                        negDict[target-sortedNums[j]]) {
                    results.push(r.concat([sortedNums[j], target-sortedNums[j]]))
                }
            }
        }
    }
    return results
};