Masalah Dua Jumlah dalam Javascript

Idea Umum

Masalah Dua Jumlah ialah masalah algoritma klasik. Ia meminta anda mencari dua nombor dalam tatasusunan yang menjumlahkan sehingga *sasaran * tertentu yang disediakan dan kemudian mengembalikan indeksnya daripada tatasusunan yang diberikan.

Pernyataan Masalah

Memandangkan tatasusunan nombor integer dan sasaran integer, kembalikan indeks bagi kedua-dua nombor supaya ia ditambah kepada sasaran. Setiap input akan mempunyai satu penyelesaian dan anda tidak boleh menggunakan elemen yang sama dua kali.

Input: angka = [2, 7, 11, 15], sasaran = 9
Output: [0, 1]
Penjelasan: nombor[0] nombor[1] = 2 7 = 9

Pendekatan 1 Brute force

Pendekatan pertama untuk sebarang masalah hanyalah dengan menyelesaikan sesuatu dan perkara yang paling mudah dari segi konsep.

Lelar melalui tatasusunan dengan dua gelung dan semak semua pasangan nombor.

const twoSum = (nums, target) => {
  for(let i = 0; i 



<h3>
  
  
  Pendekatan 1 Kerumitan
</h3>

<p><strong>Kerumitan Masa</strong> ialah <em>O(n²)</em></p>

<ol>
<li>Gelung bersarang menyemak setiap pasangan nombor</li>
<li>Menyemak setiap kombinasi yang mungkin</li>
<li>Menjadi sangat perlahan dengan tatasusunan yang besar</li>
</ol>

<p><strong>Kerumitan Angkasa</strong> ialah <em>O(1)</em><br>
1.Kami tidak mencipta struktur data baharu</p>
<h2>
  
  
  Pendekatan 2 Lebih Cekap dan apa yang kita mahu.
</h2>

<p>Kami akan menggunakan peta cincang untuk menyelesaikan perkara ini. Mari kita terangkan sedikit algoritma ini</p>

<ol>
<li>Kami menggunakan peta cincang (objek dalam JavaScript) untuk menyimpan nombor yang telah kami lihat</li>
<li>Untuk setiap nombor, kami mengira pelengkapnya (sasaran - nombor semasa)</li>
<li>Kami menyemak sama ada pelengkap itu wujud dalam peta kami</li>
<li>Jika ya, kami telah menemui dua nombor kami dan mengembalikan indeksnya</li>
<li>Jika tidak, kami menambah nombor semasa pada peta</li>
</ol>

<p>Jadi penyelesaian pertama boleh menggunakan objek JS biasa dan membina HashMap kami dengan cara itu<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>Penyelesaian kedua sebenarnya menggunakan Struktur Data Peta dalam JS. Ini membolehkan pelaksanaan yang lebih ketat dan lebih mantap, menggunakan objek Peta (diperkenalkan dalam ES6) dan selalunya diutamakan. Peta menyediakan gelagat peta cincang yang eksplisit dan mengelakkan beberapa keanehan objek JavaScript, seperti mewarisi sifat daripada Object.prototype.<br>
</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>
  
  
  Pendekatan 2 Kerumitan
</h3>

<p><strong>Kerumitan Masa</strong> ialah <em>O(n)</em></p>

<ol>
<li>Saluran tunggal melalui tatasusunan</li>
<li>Peta cincang menyediakan carian O(1)</li>
<li>Jumlah skala masa secara linear dengan saiz tatasusunan</li>
</ol>

<p><strong>Kerumitan Angkasa</strong> ialah O(n)<br>
Dalam kes yang paling teruk, kami mungkin menyimpan hampir semua nombor<br>
Tukar ganti antara masa dan kecekapan ingatan</p>

<h2>
  
  
  Kaveat
</h2>

<ol>
<li>Susun atur kosong</li>
<li>Tiada penyelesaian wujud</li>
<li>Penyelesaian berbilang boleh dilakukan. Dalam kes ini, tanya jika anda kembali selepas lelaran pertama.</li>
</ol>


          

            
        

Atas ialah kandungan terperinci Masalah Dua Jumlah dalam Javascript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!