LeetCodeの「Two-Sum」をJavaScriptで解く

最近LeetCodeで勉強しています。

今回は、記憶定着のためのアウトプットを兼ねて、「Two-Sum」という問題を紹介します。

• Two Sum - LeetCode

問題

整数が格納された配列numsと整数targetが与えられたとき、足してtargetになる2つの要素をnumsから選択し、そのインデックスを返却する。各入力には必ず1つの解があると仮定し、同じ要素を2回使用することはできない。2つの要素の返却順は問わない。

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] == 9

解法

メジャーな2種類を紹介します。

1. 総当たり法

• 時間計算量：$O(n^2)$
• 空間計算量：$O(1)$

ループをネストして2種類のインデックスを用意し、numsの要素を2つ指定してターゲットと比較していきます。下のコードでは、jループの開始をi + 1とすることで無駄なループを省いています。

const twoSum = (nums, target) => {
  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]
      }
    }
  }
}

2. ハッシュテーブル法

• 時間計算量：$O(n)$
• 空間計算量：$O(n)$

オブジェクトを利用して時間計算量を削減します。{ nums[index]: index }といった形式のオブジェクトを用意し、target - nums[i]の値がプロパティに含まれているかチェックします。

const twoSum = (nums, target) => {
  let hashTable = {}

  for (let i = 0; i < nums.length; i++) {
    hashTable[nums[i]] = i
  }

  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i]
    if (hashTable.hasOwnProperty(diff) && hashTable[diff] !== i) {
      return [i, hashTable[diff]]
    }
  }
}