Javascript: Prenez deux nombres d'un tableau et divisez le tableau en trois sous-réseaux. Trouver la somme minimum des deux nombres

Question

Il existe un tableau de N entiers. Nous allons prendre deux nombres du tableau et diviser ce tableau en trois parties. Pour être exact, nous prendrons des éléments aux indices P et Q. Et les indices des sous-réseaux seront [0, P-1], [P + 1, Q-1], [Q + 1, N-1]. Évidemment, 0 < P < Q < N-1, Q-P> 1. Nous voulons trouver la somme minimale des deux nombres. Par exemple, il existe trois façons de prendre deux nombres dans le tableau [5, 2, 4, 6, 3, 7].

• indices 1 & 3. La somme est de 8
• indices 1 & 4. La somme est 5.
• indices 2 & 4. La somme est 7.

Ainsi, le minimum somme est 5.

J'ai essayé et écrit la fonction suivante pour obtenir cet effet. De toute évidence, c'est très lent. Mais je ne peux pas penser à un moyen d'écrire des algorithmes plus rapides.

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

Voici un algorithme qui devrait fonctionner et qui présente une meilleure complexité temporelle que le vôtre.

Si arr [] stocke vos numéros dans un certain ordre, en utilisant un bon algorithme de tri (vous pouvez google it online), stockez-les dans l'ordre croissant. Stockons-les dans arr1 [].

Maintenant, arr1 [0] et arr [1] donnent la plus petite somme si arr1 [0] \ neq arr [0] \ neq arr [n]. Aussi, arr1 [1] \ neq arr [i + - 1] et arr [1] \ neq arr [0] ou arr [n]. Utilisez la recherche binaire pour vérifier les conditions.

Si ces conditions ne se tiennent pas entre arr1 [0], arr1 [1], vérifiez alors arr1 [1], arr1 [2] et ainsi de suite. Notez qu'il ne ira pas jusqu'à arr1 [n]. Au max, il peut aller à mi-chemin dans le tableau trié jusqu'à ce qu'il casse. Et n'oubliez pas de casser la boucle lorsque vous avez terminé. J'espère que ceci sert votre but!