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

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = []
Output: []

Input: nums = [0]
Output: []

Constraints

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

Solution

var threeSum = function (nums) {
    if (nums.length < 3) return [];
    nums.sort((pre, next) => pre - next);
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        if (i === 0 || nums[i] !== nums[i - 1]) {
            const d = -nums[i];
            let a = i + 1, b = nums.length - 1;
            const numMap = new Map();
            while (a < b) {
                if (nums[a] + nums[b] > d) {
                    b--;
                } else if (nums[a] + nums[b] < d) {
                    a++;
                } else {
                    const v = numMap.get(nums[a]);
                    if (!v) {
                        numMap.set(nums[a], [nums[b]]);
                    } else if (!v.includes(nums[b])) {
                        v.push(nums[b]);
                    }
                    a++;
                    b--;
                }
            }
            numMap.forEach((value, key) => {
                for (let j = 0; j < value.length; j++) {
                    res.push([nums[i], key, value[j]]);
                }
            });
        }
    }
    return res;
};