LeetCode：二和問題

twoSum 問題是一個經典的編碼挑戰，測試您的問題解決和演算法技能。

在這篇文章中，我們將首先看看一個易於理解的簡單解決方案。然後我們會逐步優化它，提高它的效率。無論您是演算法新手還是準備面試，本指南都將幫助您解決問題。讓我們開始吧！

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

讓我們看看函數應該處理的輸入和輸出。

給定數組 [2,7,11,15] 和目標 9，輸出將為 [0,1].

這是因為索引 0 和 1 處的值加起來是 9，這是目標。

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

我們會想到一個解決方案，建立一個 hashMap 將陣列中的數字儲存為鍵，將其索引儲存為值。

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

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

這是解決方案的第一部分：準備 hashMap。

在下一個迴圈中，我們檢查 hashMap 是否包含目標減去陣列中目前數字的補集。

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

如果在 hashMap 找到補集，我們就可以存取它的索引，因為我們有它的值。

然後，我們可以傳回一個包含其值（補集的索引）以及 i 的數組，i 代表當前迭代。

在此解決方案中，我們看到我們正在建立兩個單獨的循環。我們可以將它們組合成一個循環，從而節省一次迭代。

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

我們改進了條件以獲得更好的清晰度並獲得以下程式碼：

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]

以上是LeetCode：二和問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！