leetcode不定期刷題---18.四数の和

タイトルソース:力ボタンリンク:https://leetcode-cn.com/problems/4sum
n個の整数を含む配列numsとターゲット値targetを与え、numsにa+b+c+dの値がtargetと等しいように4つの要素a,b,c,dが存在するかどうかを判断する.条件を満たし、繰り返さないすべての四元グループを見つけます.
注意:
答えに重複する四元グループを含めてはいけません.
例:

     nums = [1, 0, -1, 0, -2, 2]，  target = 0。

           ：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

問題:
前の三数の和を見ると、この問題は簡単になり、三数の和の外でもう一つの循環をするだけです.
考え方:
配列をソートします.小さい順に並べ替えます.第1の数字を固定することに相当し、第2の数字を循環固定しながら、残りの数の中でtarget-nums[i]-nums[j]の2つの数字を見つけ、最後に対応する配列を構成する.
同時に重さを落とす操作は注意しなければならない.第1層が循環するとき、nums[i] > Math.abs(target) || nums[i] === nums[i-1] などがある.しかし、私のこの方法は合格しましたが、効率が低いです.

var fourSum = function(nums, target){
        nums = nums.sort((a,b)=>{return a-b});
        let arr = [];
        if(!nums || nums.length<4)return arr;
        for(let i = 0; i < nums.length-3;i++){
            if(nums[i] > Math.abs(target) || nums[i] === nums[i-1])continue;
            for(let j = i + 1; j < nums.length-2;j++){
                if(nums[j] === nums[j-1] && (j-1) !== i)continue;
                let sum = target - nums[i] - nums[j];
                let left = j+1,right = nums.length-1;
                while(left < right){
                    if(nums[left]+nums[right]>sum){
                        do{--right}while(nums[right]===nums[right+1])
                    }else if(nums[left]+nums[right] < sum){
                        do{++left}while(nums[left]===nums[left-1]);
                    }else{
                        let newArr = [nums[i],nums[j],nums[left],nums[right]];
                        arr.push(newArr);
                        do{--right}while(nums[right]===nums[right+1]);
                        do{++left}while(nums[left]===nums[left-1])
                    }
                }
            }
        }
        return arr;
    };

    ：
     :124 ms,     javascript       85.26%    
     :36.5 MB,     javascript       81.40%   

次に最適化を行い、いくつかの状況を除いた後

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
      nums = nums.sort((a,b)=>{return a-b});
        let arr = [],n = nums.length;
        if(!nums || nums.length<4)return arr;
        for(let i = 0; i < nums.length-3;i++){
            if(nums[i] > Math.abs(target) || nums[i] === nums[i-1])continue;

            let target1 = target - nums[i];
            if (nums[i + 1] + nums[i + 2] + nums[i + 3] > target1) break;
            if (nums[n - 3] + nums[n - 2] + nums[n - 1] < target1) continue;

            for(let j = i + 1; j < nums.length-2;j++){
                if(nums[j] === nums[j-1] && j>i+1)continue;

                let sum = target1 - nums[j];
                if (nums[j + 1] + nums[j + 2] > sum) break;
                if (nums[n - 2] + nums[n - 1 < sum]) continue;

                let left = j+1,right = nums.length-1;
                while(left < right){
                    if(nums[left]+nums[right]>sum){
                        right--;
                    }else if(nums[left]+nums[right] < sum){
                        left++;
                    }else{
                        let newArr = [nums[i],nums[j],nums[left],nums[right]];
                        arr.push(newArr);
                        do{--right}while(nums[right]===nums[right+1]);
                        do{++left}while(nums[left]===nums[left-1])
                    }
                }
            }
        }
        return arr;
    }

    
     :96 ms,     javascript       99.20%    
     :36.2 MB,     javascript       94.57%   

コード量がずいぶん大きくなったような気がしますが、性能面はまあまあです.