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 



<h3>
  
  
  アプローチ 1 複雑さ
</h3>

<p><strong>時間計算量</strong> は <em>O(n²)</em></p>

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

<p><strong>空間の複雑さ</strong> は <em>O(1)</em><br>
1.新しいデータ構造は作成していません</p>
<h2>
  
  
  アプローチ 2 より効率的で、私たちが望んでいること。
</h2>

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

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

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

<pre class="brush:php;toolbar:false">const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i 



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

<pre class="brush:php;toolbar:false">const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i 



<h3>
  
  
  アプローチ 2 複雑さ
</h3>

<p><strong>時間計算量</strong> は <em>O(n)</em></p>

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

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

<h2>
  
  
  注意事項
</h2>

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


          

            
        

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