優化方案：Codewars

我想在優化問題的解決方案的幫助下，我已經整理出了問題，但我的代碼是不夠好處理大陣 - codeWars : Sum of Pairs - problem 優化方案：Codewars

這裏我的代碼 -

var sum_pairs=function(e, sum){ 

var result=null; 
var arrLen=e.length; 
for(let i=0;i<arrLen-1;i++){ 
    let nextIndex=e.slice(i+1,arrLen).indexOf(sum-e[i]); 
    if(nextIndex>=0){ 
    result=[e[i],e[nextIndex+1+i]]; 
    arrLen=nextIndex+1+i; 
    } 
} 
return result; 
}

嗯，我知道這不是一個好的解決方案。無論如何，這通過所有的測試用例，但遇到大型陣列時失敗 - Result On codewars

我想知道如何優化此代碼，並學習任何技術來編寫一個好的代碼。

來源

2017-02-16 Aditya Mishra

這裏是鏈接 - https://www.codewars.com/kata/sum-of-pairs/train/javascript –

（'這裏是link' - 替換，在你的問題的圖像引用（_train/ _ part or not）。）問題不明確：什麼是_order of definition_的定義是什麼，什麼時候是一對_earlier_？如果它是_lowest index first_，那麼您只需知道是否存在與給定總和相加的不同索引值。如果它是最低指數總數，最低索引打破tie_，則需要變得更聰明......（請注意，歡迎您回答您自己的問題。） – greybeard

'我想知道如何優化此代碼' - 請勿 - 算法不能處理大數組。 '我想[...學習]任何技巧[寫作]好的代碼'你從_開始_最簡單的事情可能work_：好。你認爲每個指數都是可能的第一指數 - 看起來不可避免。目前，忽略ECMAScript'slice'的複雜性：使用'indexOf（sum-e [i]）'每個_membership query_有多少努力？總努力？什麼是需要的結果，並且一旦找到匹配對，你的'sum_pairs'會做什麼？（設想一個10000000個零的數組，總和爲零） – greybeard

一種解決方案是使用Set數據結構來記憶所有準備迭代的數字。然後我們可以檢查每個元素是否有一個數字，總和爲s。該集合具有平均常數時間複雜度，用於插入和搜索，使得該算法在時間（和空間）上是線性的。

var sum_pairs=function(ints, s){ 
    if (ints.length < 2) return undefined; //not enough numbers for pair. 
    let intSet = new Set() 
    intSet.add(ints[0]); 
    for (let i=1; i < ints.length; ++i){ 
    let needed = s-ints[i]; 
    if (intSet.has(needed)){//check if we have already seen the number needed to complete the pair. 
     return [needed,ints[i]]; 
    } 
    intSet.add(ints[i]);//if not insert the number in set and continue. 
    } 
    return undefined;//No answer found 
}

來源

2017-02-16 18:08:06

第三個例子的返回值是什麼：'sum_pairs（[10,5,2,3,7,5]，10）'？ – greybeard

它確實通過了codeWars的所有測試，所以我假設'[3,7]'。 –

太棒了，使用'set'是一個好主意，謝謝:)。 –

優化方案：Codewars

回答

相關問題