LeetCode: Masalah twoSum

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]

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 = {}
}

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
  }
}

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]]
    }
  }
}

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
  }
}

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]

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