LeetCode: twoSum 問題

twoSum 問題は、問題解決能力とアルゴリズム スキルをテストする古典的なコーディングの課題です。

この投稿では、まず、理解しやすい簡単な解決策を見ていきます。次に、段階的に最適化して効率を向上させます。アルゴリズムを初めて使用する場合でも、面接の準備をしている場合でも、このガイドは問題を解決するのに役立ちます。始めましょう!

let inputArray = [2, 7, 11, 15]
let target = 9
console.log(twoSum(inputArray, target)) // Output: [0, 1]

関数が処理する入力と出力を見てみましょう。

配列 [2,7,11,15] とターゲット 9 を指定すると、出力は [0,1] になります。

これは、インデックス 0 と 1 の値を合計すると、ターゲットである 9 になるためです。

function twoSum(nums, target) {
  const hashMap = {}
}

配列内の数値をキーとして、そのインデックスを値として格納する hashMap を作成する解決策を考えます。

function twoSum(nums, target) {
  const hashMap = {}

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

これはソリューションの最初の部分です。hashMap の準備です。

次のループでは、配列内の現在の数値を引いたターゲットの補数が hashMap に含まれているかどうかを確認します。

function twoSum(nums, target) {
  const hashMap = {}

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

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

    if (hashMap[complement] !== undefined && hashMap[complement] !== i) {
      return [i, hashMap[complement]]
    }
  }
}

補数が hashMap で見つかった場合は、その値があるため、そのインデックスにアクセスできます。

次に、現在の反復を表す i とともにその値 (補数のインデックス) を含む配列を返すことができます。

このソリューションでは、2 つの別々のループを作成していることがわかります。それらを 1 つのループに結合することで、1 回の反復を節約できます。

function twoSum(nums, target) {
  const hashMap = {}

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

    if (hashMap[complement] !== undefined && hashMap[complement] !== i) {
      return [i, hashMap[complement]]
    }
    hashMap[nums[i]] = i
  }
}

より明確にするために条件を改良し、次のコードを取得しました:

function twoSum(nums, target) {
  const hashMap = {}

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

    if (complement in hashMap) {
      return [i, hashMap[complement]]
    }
    hashMap[nums[i]] = i
  }
}

let inputArray = [2, 7, 11, 15]
let target = 9
console.log(twoSum(inputArray, target)) // Output: [0, 1]

以上がLeetCode: twoSum 問題の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。