Javascript：從數組中取兩個數字並將數組分成三個子數組。找到兩個數字的最小和

Question

有一個N個整數的數組。我們將從數組中取兩個數字，並將這個數組分成三部分。準確地說，我們將採用索引P和Q處的元素。子陣列的索引將爲[0，P-1]，[P + 1，Q-1]，[Q + 1，N-1]。顯然，0 < P < Q < N-1，Q-P> 1.我們想找到兩個數的最小和。

例如，有三種方法可以從數組中取兩個數字[5,2,4,6,3,7]。

• 指數1 & 3.總和是8
• 指數1 & 4.總和是5
• 指數2 & 4.總和是7

所以最小總和爲5.

我已經試過並編寫了下面的函數來實現這個效果。顯然它非常緩慢。但我想不出一種更快的算法。

const arrayOne = [5, 2, 4, 6, 3, 7] 
console.log(arrayOne) 

const breakChain = (arr) => { 
let lowest = 2000000000 
for (let open = 1; open < arr.length - 3; open ++) { 
    for (let close = open + 2; close < arr.length - 1; close ++) { 
    const low = arr[open] + arr[close] 
    if (low < lowest) { 
    lowest = low 
    } 
    } 
} 
console.log(lowest) 
} 

breakChain(arrayOne) 

Answer 1

這是一個算法，它應該可以工作，並且與您的算法相比具有更好的時間複雜度。

如果arr []以某種順序存儲您的數字，那麼使用一個好的排序算法（您可以在線將其谷歌），以升序存儲它們。讓我們將它們存儲在arr1 []中。

現在，如果arr1 [0] \ neq arr [0] \ neq arr [n]，arr1 [0]和arr [1]將產生最小和。此外，arr1 [1] \ neq arr [i + - 1]和arr [1] \ neq arr [0]或arr [n]。使用二進制搜索來檢查條件。

如果這些條件在arr1 [0]，arr1 [1]之間不成立，則檢查arr1 [1]，arr1 [2]等。請注意，它不會去arr1 [n]。在最大值時，它可能會通過已排序的數組中途到中斷。並且記住當你完成時打破循環。

我希望這可以達到您的目的！