[leetcode]問題解答と解説。18. 4Sum [JavaScript]

皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます

私はある決意をして今挑んでいます。
モチベーションを保つためだけにこれをやっています。

では今日のleetCode。
【[leetcode]18. 4Sum】の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。

※下にある自分のコードは自分で設けた制限時間内に書けたところまです。

これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。

[leetcode]18. 4Sum ルール

ざっくり和訳

exampleは[実際の問題ページ(https://leetcode.com/problems/4sum/)を見てください

[leetcode]18. 4Sum 問題ページ

18. 4Sum

[leetcode]18. 4Sum

my code is not good(worng)

とりあえず愚直に書いたやつ。(恥ずかしいですが..)
順番に移動するのではなく特定の場所を探さないといけない

 function fourSum(nums, target) {
    let length = nums.length -1
    let one = 0, two = 1, three = 2, four = 3;
    let result = []
    console.log(one, two, three, four)
    while(one !== length){
        if(nums[one] + nums[two] + nums[three] + nums[four] === target){
            result.push([nums[one], nums[two], nums[three], nums[four]])
        }
        one++
        two++
        three++
        four++
        if(two === nums.length){
            two = 0
        }
         if(three === nums.length){
            three = 0
        }
         if(four === nums.length){
            four = 0
        }

    }
    return result
};

fourSum([1, 0, -1, 0, -2, 2], 0)

[leetcode]18. 4Sum。discussの中の一つの解答例

数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれないですね

JavaScriptでfilterされている、discussはこちらから

これが違う実装

leetCode 18. 4Sum

1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    nums.sort((a, b) => a - b); // 並び順を整える
    const result = []

    for(let i = 0; i < nums.length - 3; i++) { // 0番目から3番目まで
        for(let j = i + 1; j < nums.length - 2; j++) { // 1番目から。最後から2番目まで
            let low = j + 1; // 2番目から
            let high = nums.length - 1 // 最後から
            // [0, 1, 2, 3, 4] 今全てがpointer参照されている
            // or
            // [0, 1, 2, 3, 4, 5 ,6, 7] 0-2と7が参照されている

            while(low < high) {
                const sum = nums[i] + nums[j] + nums[low] + nums[high];
                if(sum === target) {
                    result.push([nums[i], nums[j], nums[low], nums[high]])
                    while(nums[low] === nums[low + 1]) low++; // 同じ値のうちは移動
                    while(nums[high] === nums[high - 1]) high--;
                    low++; // 同じ値ではない次の値
                    high--; // 同じ値ではない次の値
                } else if(sum < target) {
                    low++ // 一番低い値を移動する。lowを動かしてjの移動さきを作る
                } else {
                    high--
                }
            }  
            while(nums[j] === nums[j + 1]) j++;　 //同じ値はチェック済みなのでスキップする
        }   
        while(nums[i] === nums[i + 1]) i++; //同じ値はチェック済みなのでスキップする
    }
    return result
};

[leetcode]18. 4Sumをやってみて感想

• ポインタの移動のさせ方!!
• どうもパフォーマンス考えてo(n2)とかを避けていたが当然せざるを得ないこともある

カテゴリー leetCode