LeetCodeデビュー戦が大敗北すぎた件について - テックキャンプ卒の弱々エンジニア日記

こんにちは、Tochiです。昨日の夜、「世界一流エンジニアの思考法」を読んでいたところ、 LeetCodeのススメについて記載があったのでさっそくデビューしてきました。

books.bunshun.jp

コーディング面接で使われる問題の学習サイトで、GAFA等の外資系企業の面接対策として有効なようです。好きな言語を選んで問題を解くと、自分が書いたコードが他の人のコードに比べてどれくらい適切な書き方をしているのかがわかるようになっています。

どんな問題だったのか。

デビュー戦はまず簡単なものを！と思い下記のような問題を選びました。

問題

与えられた整数の配列 nums と整数 target があります。nums 内の二つの要素を選んで足すと target になるような要素のインデックスを返してください。

各入力には正確に一つの解があるものとし、同じ要素を二度使用することはありません。返す順番は任意です。

例:

入力: nums = [2,7,11,15], target = 9

出力: [0,1]

説明: nums[0] + nums[1] == 9 なので、[0, 1] を返します。

制約:

2 <= nums.length <= 10⁴

-10⁹ <= nums[i] <= 10⁹

-10⁹ <= target <= 10⁹

これを見て最初に思ったのは楽勝じゃんwwwwって感じでした。

どのようにアプローチしたのか。

私の方針としては、与えられた配列numsを順にforEachかなにかで１つずつ見ていき、合計値targetと今参照している値numとの差分target - numに値する数字がどこにあるかを探す。といったいかにも凡人が考えそうな考え方で始めました。。

実際のコード

function twoSum(nums: number[], target: number): number[] {
    let result: number[] = [];

    nums.forEach((num, index) => {
        const anotherNums: number[] = nums.slice(index + 1);
        const anotherIndex = anotherNums.findIndex(anotherNum => anotherNum === target - num);

        if (anotherIndex >= 0) {
            result = [index, anotherIndex + index + 1];
            return false;
        }
    });

    return result;
}

結果はどうだったのか？

みてください、、この惨敗具合。伸び代しかありません！！！！！！！！！（笑）

再度チャレンジ！！(連想配列)

まずは配列操作の発想を連想配列でできないか考えてみました。実装したコードはこんな感じです。

連想配列に[差分: インデックス]としていく感じにしました。

function twoSum(nums: number[], target: number): number[] {
    let result: number[] = [];
    let numAndAnother: { [key: number]: number } = {};

    nums.forEach((num, index) => {
        if (numAndAnother[num] !== undefined) {
            result = [numAndAnother[num], index];
            return;
        }
        numAndAnother[target - num] = index;
    });

    return result;
}

すると結果はそこそこ良くなりました！！！

ただ、まだ平均（ボリュームゾーン）に達していないので、さらに改善を加えていきます。

さらに改善

ここで、少しカンニング。他の方がどんな感じで実装していたかをみてみます。すると結構似たようなコードだったりします。

なので、無駄な変数などを削ぎ落としていきます。そうすると、forEachではなくforになりそうです管理すべき変数がかなり減りました. ついでにnumAndAnother[nums[index]] !== undefinedを少し変えてみました。

function twoSum(nums: number[], target: number): number[] {
    let numAndAnother: { [key: number]: number } = {};

    for (let index = 0; index < nums.length; index++) {
        if (numAndAnother.hasOwnProperty(target - nums[index])) {
            return [numAndAnother[target - nums[index]], index];
        }
        numAndAnother[nums[index]] = index;
    }

    return [];
}

ん〜〜〜〜〜

ここで鬼のカンニング

ちょっとサンプルコードみてみます。

function twoSum(nums: number[], target: number): number[] {
    const seen = {};

    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];

        if (seen.hasOwnProperty(diff)) {
            return [seen[diff], i];
        }

        seen[nums[i]] = i;
    }

    return [];
};

やっていること自体は一緒そうなのですよね。。。。あ、target - nums[index]が繰り返し使われているから変数におかなきゃ。。。 (変数においたら同じような結果に！)

メモリ使用量について

メモリ使用量については、、サンプルコードで色々触ってみた感じランタイムが激落するので過度な追及はしませんでした。。。

まとめ

今回、LeetCodeに初挑戦してみました。ひとまずは難しいものよりも簡単なものをとにかく積み上げていく感じで進めていきたいと思います！！！