【LeetCode】1.Two Sum #Typescript

問題原文

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

日本語訳

整数からなる配列numsと整数targetが与えられたとき、numsから2つを足し合わせるとtargetになる2つの数のindicesを返してください。

targetとなる組み合わせは1つしか存在せず、同じ数字は1度しか使ってはいけません。

答えを返す順番は自由です。

解法(全探索)

おそらく全人類の8割が最初はこの解法で解くのではないだろうか？
for文を入れ子にした全探索である。

function twoSum(nums: number[], target: number): number[] {
    for(let i = 0; i < nums.length; i++){
        for(let j = i + 1; j < nums.length; j++){
            if(nums[i] + nums[j] == target){
                let result : number[] = [i, j];
                return result;
            }
        }
    }
};

O(n)を目指す

問題文の最後に添えられているこの一文
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
訳：O（n^2)未満で考えてみましょう

解法O(n)

O(n)にする場合for文は1度しか使えないので、1度のループで2つの整数をチェックする必要がある。
ではどのようにして数値を導き出すのか、ここで重要になるのがtarget - 任意の値という考え方。
target - 任意の値の結果がnums内に存在していればtargetになる2数が導き出せる。
コードに落とし込むとこんな感じ

function twoSum(nums: number[], target: number): number[] {
    // Map初期化
    const map = new Map<number, number>();

    for(let i: number = 0; i < nums.length; i++){
        // target - nums[i]をわかりやすくsubとしておく
        const sub: number = target - nums[i];

        // subがMapに含まれていたら現在のindexとsubのindexを返す
        if(map.has(sub)){
            return [i, map.get(sub)];
        }

        // なかった場合数値をKeyとしてMapに追加
        map.set(nums[i], i);
    }
};

かなり計算量が抑えられたコードが書けました。
ちなみに、私は解説を読むまでこの解法を思いつくことはできませんでした。
今まで計算量を意識して学習してこなかった弊害ですね…
つよつよエンジニアへの道は遠い……