Rumah > hujung hadapan web > tutorial js > LeetCode: Masalah twoSum

LeetCode: Masalah twoSum

DDD
Lepaskan: 2024-12-13 07:24:12
asal
888 orang telah melayarinya

LeetCode: twoSum Problem

Masalah twoSum ialah cabaran pengekodan klasik yang menguji kemahiran menyelesaikan masalah dan algoritma anda.

Dalam siaran ini, mula-mula kita akan melihat penyelesaian mudah yang mudah difahami. Kemudian, kami akan mengoptimumkannya langkah demi langkah untuk meningkatkan kecekapannya. Sama ada anda baru dalam algoritma atau bersedia untuk temu duga, panduan ini akan membantu anda menguasai masalah tersebut. Mari mulakan!

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

Mari kita lihat input dan output yang harus dikendalikan oleh fungsi.

Memandangkan tatasusunan [2,7,11,15] dan sasaran 9, output akan menjadi [0,1].

Ini kerana nilai pada indeks 0 dan 1 menambah sehingga 9, yang merupakan sasaran.

function twoSum(nums, target) {
  const hashMap = {}
}
Salin selepas log masuk

Kami akan memikirkan penyelesaian di mana kami mencipta Peta hash untuk menyimpan nombor dalam tatasusunan sebagai kunci dan indeksnya sebagai nilai.

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

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

Ini ialah bahagian pertama penyelesaian: menyediakan Peta hash.

Dalam gelung seterusnya, kami menyemak sama ada hashMap mengandungi pelengkap sasaran tolak nombor semasa dalam tatasusunan.

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]]
    }
  }
}
Salin selepas log masuk

Jika pelengkap ditemui dalam hashMap, kita boleh mengakses indeksnya kerana kita mempunyai nilainya.

Kemudian, kita boleh mengembalikan tatasusunan yang mengandungi nilainya (indeks pelengkap) bersama-sama dengan i, yang mewakili lelaran semasa.

Dalam penyelesaian ini, kami melihat bahawa kami mencipta dua gelung berasingan. Kita boleh menggabungkannya menjadi satu gelung, dengan itu menjimatkan satu lelaran.

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
  }
}
Salin selepas log masuk

Kami memperhalusi syarat untuk kejelasan yang lebih baik dan memperoleh kod berikut:

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]

Salin selepas log masuk

Atas ialah kandungan terperinci LeetCode: Masalah twoSum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

sumber:dev.to
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan