leetcode 15.三数之和 javascript

原理其实很简单，但是只是时间复杂度是个很大的考虑

我最开始用的暴力法，三个for循环，时间复杂度是n3，leetcode直接超时 -_-

所以被迫改成这种版本，复杂度是n2

话不多说直接看代码就好了

/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
    let result = [];
    let uniqueMap = {};
    //由小到大排序
    nums = nums.sort((x, y) => x - y);
    for(let i = 0; i < nums.length - 2; i++){
        //排序之后会有很多重复数字，直接跳过可以省去不少时间
        if( i > 0 && nums[i] === nums[i-1]) continue;
        let L = i + 1,
            R = nums.length -1;
        while(L < R){
            //判断是否是答案，并避免重复
            if(L < R && nums[L] + nums[R] + nums[i] === 0 && !uniqueMap[`${nums[i]}${nums[L]}${nums[R]}`]) {
                result.push([nums[i], nums[L], nums[R]]);
                uniqueMap[`${nums[i]}${nums[L]}${nums[R]}`] = true;
            }

            if(nums[L] + nums[R] + nums[i] < 0) {
                L++
            } else {
                R--;
            }
        }
    }
    return result;
};