今日kata

原始題目如下:(5kyu)
Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.

翻譯:
給一陣列ints及一總和sum，陣列中包含許多整數int，須由左至右找出一組兩個int，其相加為sum。

範例:

sum_pairs([11, 3, 7, 5],         10)
//             ^--^      3 + 7 = 10
== [3, 7]

sum_pairs([0, 0, -2, 3], 2)
// 沒有任何兩個數字相加為2 
== undefined 

sum_pairs([10, 5, 2, 3, 7, 5],         10)
//             ^-----------^   5 + 5 = 10, indices: 1, 5
//                   ^--^      3 + 7 = 10, indices: 3, 4 *
// * entire pair is earlier, and therefore is the correct answer
// * 回傳較早完整的被找到的那組
== [3, 7]

構想&解法

這題起初卡在效能沒過這關，原先解法如下:

var sum_pairs = function(ints, s) { 
  let match = []
  for (let i = 0; i < ints.length; i++) {
    if (i > Math.max(...match) && match.length !== 0) break;

    let partner = s - ints[i];
    if (ints.indexOf(partner) !== i && ints.indexOf(partner) >= 0) {
      if (match.length === 0 || Math.max(i, ints.indexOf(partner)) < Math.max(...match)) {
        match = [i, ints.indexOf(partner)]
      }
    }
  }
  if (match.length === 0) return undefined
  match.sort()

  return [ints[match[0]], ints[match[1]]]

}

• 宣告一空陣列match，負責放符合的element index
• for loop一一遍歷ints[i]，尋找ints陣列中是否有符合的partner (partner=sum-ints[i])
• 記下ints[i]和partner[i]
• 將index最小組合存入match
  這邏輯用文字敘述好繞...難怪效能不過

卡了兩天...最後還是上網尋求解題概念!　

最終使用Set()不重複的特性，又再重新重構一番:

var sum_pairs = function(ints, s) {
 let stack=new Set()
 stack.add(ints[0])
 for(let i=1; i<ints.length;i++){
   let match=s-ints[i]
   if(stack.has(match)){
     return [match,ints[i]]
   }
   stack.add(ints[i])
 }
 return undefined

}

• 宣告一stack為Set，先將ints[0]放入stack中
• 從位置1開始一一遍歷ints陣列
• 先算出目前ints[i]的match (match=sum-ints[i])
• 確認stack中的所有item是否有match
• 若有就return結果，若無就繼續check下一個ints[i]的match是否有在stack中存在!

當要自己畫圖解說時，才知道很難把動態的思路畫清楚.....

其他解法觀摩

var sum_pairs=function(ints, s){
  var seen = {}
  for (var i = 0; i < ints.length; ++i) {
    if (seen[s - ints[i]]) return [s - ints[i], ints[i]];
    seen[ints[i]] = true
  }
}

先印出來看seen的內容

概念類似，seen物件中的屬性是ints中的元素，一一判斷seen中是否有和ints[i]相加為sum的屬性存在。

整理用法

Set物件

set物件中的每一個值只會出現一次! 唯一! (不需要key)

以下內容及範例取自Javascript.info-Map and Set

主要Methods:

• net Set (iterable): 建立set
• set.add(value): 增加value，回傳set本身
• set.delete(value): 刪除value，回傳true/false
• set.has(value): 如果set有該value存在，回傳true
• set.clear(): 清空所有set的內容
• set.size: 元素數量

當對相同的value重複執行set.add(value)，不會影響set，因為任何值都是唯一。

範例:

let set = new Set();

let john = { name: "John" };
let pete = { name: "Pete" };
let mary = { name: "Mary" };

// visits, some users come multiple times
set.add(john);
set.add(pete);
set.add(mary);
set.add(john);
set.add(mary);

// set keeps only unique values
alert( set.size ); // 3

for (let user of set) {
  alert(user.name); // John (then Pete and Mary)
}

以上為今日分享的內容，若有錯誤或是建議，請再隨時和我聯繫。