LeetCode 2日目

LeetCode ２日目の復習やっていきます。

１日目の方に書き忘れてましたが、NeetCodeのRoadmapを参考に進めてます。

1. Two Sum

配列の内２つの数値を加算することで指定の値にできる要素の添え字を返す問題

自分のコード

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        const pare = target - nums[i];

        const pareIndex = nums.findIndex((ele, key) => key !== i && ele === pare);

        if (pareIndex !== -1) {
            return [i, pareIndex];
        }

    }
    
    return [];
};

配列をループして指定の値から引いた値が自身の要素以外に存在するか配列に存在するか確認している。 計算量はO(n²)となっている。

ランキング上位のコード

function twoSum(nums: number[], target: number): number[] {
    let numberMap = new Map<number, number>();

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

        if (numberMap.has(diff)) {
            return [numberMap.get(diff), i];
        }

        numberMap.set(number, i);
    }

    return [-1, -1]
};

これもハッシュを使うことで計算量を少なくできる。

間違ってるかもしれないけど、計算量的にはO(n)になるのかな？

工夫としてキーに値を入れている、そうすることで値のチェックがO(1)で出来るようになっている。

昨日ハッシュ使うぞーって言ったばっかりなのに使えなかったー

原理を理解しきれていないから応用できないのかな。。。

今日は１問だけです。ではまた！