iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 29
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 29

Day29-解題-Two Sum

這次的題目如下:
給定一個包含多個數字的陣列和一個目標值,然後從陣列裡面找出兩個數,兩個相加正好等於該目標值,要注意數字不可以被重複使用,陣列裡也可能有多種組合相加正好等於目標值,最後回傳所有找到組合的陣列索引值。

ex:
[1, 2, 3, 6, 7],目標值為9: 最後回傳 [1, 4],[2, 3]

理解題目後我們來實作吧!

  1. 宣告 twoSum() 函式,帶入陣列和目標值兩個參數,接著我們要利用 JS 物件的特性來解題,因此建立一個 map 物件,還有宣告一個儲存結果的空陣列。
function twoSum(arr, target) {
  let result = [];
  let map = {};
  for (let i = 0; i < arr.length; i++) {
    
  }
  console.log(map);
  return result;
}
  1. 接著在迴圈內利用目標值減當前陣列元素的值,建立 minusNum,並善用物件的特性,讓元素值和索引值存入物件內。

  2. 接著判斷只要當插值存在於 map 物件的話,就代表當前的 arr[i] 和 minusNum 相加為目標值,因此可以將此兩個數字的索引加入 result 最終結果的陣列內。

ex: 陣列為 [1, 2],目標值為3
i = 0時,minusNum = 2,map[arr[0]] = 0(map[1] = 0),map[2] 為undefined,不會記錄到結果陣列。
i = 1時,minusNum = 1,map[arr[1]] = 1(map[2] = 1),map[1] 為0,因此可將兩個索引 [0, 1] 加到結果。

function twoSum(arr, target) {
  let result = [];
  let map = {};
  for (let i = 0; i < arr.length; i++) {
    let minusNum = target - arr[i]; // 把當前i元素的插值記錄下來
    // 用map記錄值和索引
    map[arr[i]] = i; // arr[i]: 數字值,i: 索引值

    if(map[minusNum] !== undefined) { // 當插值存在的情況下,新增插值的索引和i
      result.push([map[minusNum], i]);
    }
  }
  console.log(map);
  return result;
}

console.log(twoSum([7, 2, 12, 6, 1, 3], 9));

運行結果如下所示,順便也把 map 的內容印出來了哈哈~

這次的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day29-two-sum.js

明天我們將用回溯法實作"Subsets"問題,然後就完成鐵人賽了(感動!!/images/emoticon/emoticon02.gif


上一篇
Day28-解題-Ransom Note
下一篇
Day30-解題-Subsets
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言