整體思路

二和問題是一個經(jīng)典的演算法問題。它要求您在數(shù)組中查找兩個數(shù)字，它們的總和達(dá)到所提供的特定 * 目標(biāo) *，然後從給定數(shù)組中返回它們的索引。

問題陳述

給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)，傳回兩個數(shù)字的索引，使它們相加等於目標(biāo)。每個輸入都只有一個解決方案，而且您不能兩次使用相同的元素。

輸入：nums = [2, 7, 11, 15]，目標(biāo) = 9
輸出：[0, 1]
解釋： nums[0] nums[1] = 2 7 = 9

方法1 暴力破解

解決任何問題的第一個方法可能就是完成某件事，並且是概念上最簡單的事情。

用兩個循環(huán)迭代數(shù)組並檢查所有數(shù)字對。

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

方法 1 複雜性

時間複雜度為O(n2)

1. 巢狀循環(huán)檢查每對數(shù)字
2. 檢查每個可能的組合
3. 使用大數(shù)組時變得非常慢

空間複雜度為O(1)
1.我們沒有建立新的資料結(jié)構(gòu)

方法 2 更有效率，這就是我們想要的。

我們將使用哈希映射來解決這個問題。讓我們稍微解釋一下這個演算法

1. 我們使用哈希映射（JavaScript 中的物件）來儲存我們看到的數(shù)字
2. 對於每個數(shù)字，我們計算其補(bǔ)碼（目標(biāo) - 當(dāng)前數(shù)字）
3. 我們檢查補(bǔ)集是否存在於我們的地圖中
4. 如果是，我們就找到了兩個數(shù)字並回傳它們的索引
5. 如果沒有，我們將目前號碼加入地圖

所以第一個解決方案可能是使用常規(guī) JS 物件並以這種方式建構(gòu)我們的 HashMap

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

第二種解決方案實(shí)際上是在 JS 中使用 Map 資料結(jié)構(gòu)。這允許更嚴(yán)格、更健壯的實(shí)現(xiàn)，使用 Map 物件（在 ES6 中引入）並且通常是首選。 Map 提供明確雜湊映射行為，並避免 JavaScript 物件的一些怪癖，例如從 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));

方法 2 複雜性

時間複雜度為O(n)

1. 單次遍歷數(shù)組
2. 雜湊映射提供 O(1) 查找
3. 總時間與陣列大小成線性關(guān)係

空間複雜度 為 O(n)
在最壞的情況下，我們可能會儲存幾乎所有數(shù)字
時間和記憶體效率之間的權(quán)衡

注意事項

1. 空數(shù)組
2. 不存在解決方案
3. 有多種解決方案。在這種情況下，詢問您是否在第一次迭代後返回。

以上是JavaScript 中的二和問題的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！