JavaScript の 2 つの和の問題

一般的な考え方

Two Sum 問題は、古典的なアルゴリズムの問​​題です。これは、指定された特定の *ターゲット * に合計される 2 つの数値を配列内で見つけて、指定された配列からそれらのインデックスを返すように求めます。

問題提起

整数 nums の配列と整数ターゲットが与えられた場合、合計がターゲットになるように 2 つの数値のインデックスを返します。各入力にはソリューションが 1 つだけあり、同じ要素を 2 回使用することはできません。

入力: 数値 = [2, 7, 11, 15]、ターゲット = 9
出力: [0, 1]
説明: nums[0] nums[1] = 2 7 = 9

アプローチ 1 ブルートフォース

どんな問題でも最初のアプローチは、何かを成し遂げること、そして概念的に最も簡単なことを実行することかもしれません。

2 つのループで配列を反復処理し、数値のすべてのペアをチェックします。

const twoSum = (nums, target) => {
  for(let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      console.log(` i is ${nums[i]} and k is ${nums[j]}`)
      // lets check if we add the 2 numbers if it equals target
      if (target === nums[i] + nums[j]) {
        return [i, j]
      }
    }
  }
};

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));

アプローチ 1 複雑さ

時間計算量 は O(n²)

1. すべての数値ペアをチェックする入れ子ループ
2. 可能なすべての組み合わせをチェックします
3. 配列が大きいと非常に遅くなります

空間の複雑さ は O(1)
1.新しいデータ構造は作成していません

アプローチ 2 より効率的で、私たちが望んでいること。

これを解決するためにハッシュ マップを使用します。このアルゴリズムについて少し説明しましょう

1. 見た数値を保存するためにハッシュ マップ (JavaScript のオブジェクト) を使用します
2. 各数値について、その補数 (ターゲット - 現在の数値) を計算します
3. マップ内に補体が存在するかどうかを確認します
4. そうであれば、2 つの数値が見つかり、それらのインデックスが返されます
5. そうでない場合は、現在の番号をマップに追加します

最初の解決策は、通常の JS オブジェクトを使用し、その方法で HashMap を構築することです

const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i] 

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

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimizedRegularObject(nums, target));

2 番目の解決策は、実際には JS で Map データ構造を使用することです。これにより、Map オブジェクト (ES6 で導入) を使用して、より厳密で堅牢な実装が可能になり、多くの場合好まれます。 Map は明示的なハッシュ マップの動作を提供し、Object.prototype.
からのプロパティの継承など、JavaScript オブジェクトのいくつかの特殊な動作を回避します。

const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i]

    if (mapOfStuff.has(complement)) {
      return [mapOfStuff.get(complement), i]
    }
    mapOfStuff.set(nums[i], i)
  }

}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimized(nums, target));

アプローチ 2 複雑さ

時間計算量 は O(n)

1. 配列を単一パスで通過
2. ハッシュ マップは O(1) ルックアップを提供します
3. 合計時間は配列サイズに比例して増加します

空間の複雑さ は O(n)
最悪の場合、ほぼすべての数値が保存される可能性があります
時間とメモリ効率のトレードオフ

注意事項

1. 空の配列
2. 解決策は存在しません
3. 複数の解決策が可能です。この場合、最初の反復後に戻るかどうかを尋ねます。

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