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 < 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));

Pendekatan 1 Kerumitan

Kerumitan Masa ialah O(n²)

1. Gelung bersarang menyemak setiap pasangan nombor
2. Menyemak setiap kombinasi yang mungkin
3. Menjadi sangat perlahan dengan tatasusunan yang besar

Kerumitan Angkasa ialah O(1)
1.Kami tidak mencipta struktur data baharu

Pendekatan 2 Lebih Cekap dan apa yang kita mahu.

Kami akan menggunakan peta cincang untuk menyelesaikan perkara ini. Mari kita terangkan sedikit algoritma ini

1. Kami menggunakan peta cincang (objek dalam JavaScript) untuk menyimpan nombor yang telah kami lihat
2. Untuk setiap nombor, kami mengira pelengkapnya (sasaran - nombor semasa)
3. Kami menyemak sama ada pelengkap itu wujud dalam peta kami
4. Jika ya, kami telah menemui dua nombor kami dan mengembalikan indeksnya
5. Jika tidak, kami menambah nombor semasa pada peta

Jadi penyelesaian pertama boleh menggunakan objek JS biasa dan membina HashMap kami dengan cara itu

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));

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.

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));

Pendekatan 2 Kerumitan

Kerumitan Masa ialah O(n)

1. Saluran tunggal melalui tatasusunan
2. Peta cincang menyediakan carian O(1)
3. Jumlah skala masa secara linear dengan saiz tatasusunan

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

Kaveat

1. Susun atur kosong
2. Tiada penyelesaian wujud
3. Penyelesaian berbilang boleh dilakukan. Dalam kes ini, tanya jika anda kembali selepas lelaran pertama.

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