[Leet Code] 01 Two Sum

今日から1日1Leet Code!
記念すべき1回目！

1. Two Sum
   int型配列と整数が渡され、配列の要素のうち和が与えられた整数になる2要素を求める問題
   2回ループを回すことで無事に解けた

TwoSum.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const ans_array = [];
    const leng = nums.length;
    for(let i = 0; i<leng; i++){
            for(let j=i+1; j<leng; j++){
                if(nums[i] + nums[j] === target){
                    ans_array.push(i);
                    ans_array.push(j);
                    return ans_array;
                }
            }       
    }
};

改善点
2回ループを回しているため計算量が大きい
→ハッシュマップを使ってループを1回に

ハッシュマップとは...
キーと値の組み合わせで要素を管理する
配列は番号で管理する

参照

afterTwoSum.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const pairIdx = {};

    for(let i = 0; i<nums.length; i++){
        const num = nums[i]; //今見てるnum
        if(target - num in pairIdx){
            return [i, pairIdx[target - num]];
        }
        pairIdx[num] = i;

    }
    
};