Javascript：从数组中取两个数字并将数组分成三个子数组。找到两个数字的最小和

-2

有一个N个整数的数组。我们将从数组中取两个数字，并将这个数组分成三部分。准确地说，我们将采用索引P和Q处的元素。子阵列的索引将为[0，P-1]，[P + 1，Q-1]，[Q + 1，N-1]。显然，0 < P < Q < N-1，Q-P> 1.我们想找到两个数的最小和。Javascript：从数组中取两个数字并将数组分成三个子数组。找到两个数字的最小和

例如，有三种方法可以从数组中取两个数字[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)

来源

2017-10-16 S. Will

这是一个家庭作业。自己试试 – Weedoze

请显示你的尝试。 Stackoverflow不是免费的代码编写或教程服务。目标是帮助你解决**你的代码** – charlietfl

@charlietfl我自己尝试过。显然它不是世界上最快的算法。 –

这是一个算法，它应该可以工作，并且与您的算法相比具有更好的时间复杂度。

如果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]。在最大值时，它可能会通过已排序的数组中途到中断。并且记住当你完成时打破循环。

我希望这可以达到您的目的！

来源

2017-10-16 16:25:44 Mathbg

Javascript：从数组中取两个数字并将数组分成三个子数组。找到两个数字的最小和

回答

相关问题