リートコード tow sum

tow sum

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.

与えられた配列の和で、targetとなる組み合わせを探す。

example 1:
Input: nums = [2,7,11,15], target=9
Output: [0,1]
配列の0番目と1番目の和が9となるから

One-pass Hash Table

example 1:
Input: nums = [2,7,11,15], target=9
Output: [0,1]
配列の0番目と1番目の和が9となるから

curをnumsのi番目の数とする。
xは整数とする。

このとき、
cur + x = target
x = target - cur
となる。

もし x がnumsに含まれていれば、それが答えとなる

コード

const twoSum = (nums: number[], target: number): number[] => {
    const map = new Map<number, number>();
    for (let xIndex = 0; xIndex < nums.length; xIndex++) {
        const cur = nums[xIndex];
        const x = target - cur;
        
        const yIndex = map.get(x);
        if (yIndex !== undefined) {
            return [yIndex, xIndex];
        }
        // 探す用のmapを作る. 同じ値を探す手間を省く
        map.set(cur, xIndex);
    }
    return [];
}

力まかせ探索

すべてのパターンを試して、targetの値が出れば終わり。
計算量は$O(n^2)$
numsの長さが2なら$2^2=4$回for文が回る
numsの長さ3なら$3^3=9$回for文が回る

コード

const 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) {
                return [i, j]
            }
        }
    }
    return []
}

2 パス ハッシュ テーブル

numsのi番目の数字から、ほしい相方の番号が分かる。
相方の番号があればそれぞれのindexをreuturnする
計算量は$O(n)$

コード

Mapを使った場合
62ms

const twoSum = (nums: number[], target: number): number[] => {
    const map = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], i);
    }
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement) && map.get(complement) !== i) {
            return [i, map.get(complement)];
        }
    }
}

Mapを使わず直接、numsを使った場合
142ms

const twoSum = (nums: number[], target: number): number[] => {
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
            if (nums.indexOf(complement) !== -1 && nums.indexOf(complement) !== i) {
            return [i, nums.indexOf(complement)];
        }
    }
}

Mapを使うかの有無で時間が結構変わるのね。びっくり
時間はleetcodeの結果。