JavaScript 中的二和問題

整體思路

二和問題是一個經典的演算法問題。它要求您在數組中查找兩個數字，它們的總和達到所提供的特定 * 目標 *，然後從給定數組中返回它們的索引。

問題陳述

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

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

方法1 暴力破解

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

用兩個循環迭代數組並檢查所有數字對。

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(n²)

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

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

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

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

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

所以第一個解決方案可能是使用常規 JS 物件並以這種方式建構我們的 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));

第二種解決方案實際上是在 JS 中使用 Map 資料結構。這允許更嚴格、更健壯的實現，使用 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. 單次遍歷數組
2. 雜湊映射提供 O(1) 查找
3. 總時間與陣列大小成線性關係

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

注意事項

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

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