Trouver trois éléments dans un tableau dont la somme est plus proche d’un nombre donné

Question

Étant donné un tableau d'entiers, Un₁, Un₂, ..., _n, y compris les aspects positifs et négatifs, et un autre entier S. Maintenant, nous devons trouver trois différents entiers dans le tableau, dont la somme est la plus proche du nombre entier donné S. S'il existe plus d'une solution, l'un d'eux est ok.

Vous pouvez supposer que tous les entiers sont dans int32_t gamme, et pas de dépassement de capacité se produit avec le calcul de la somme. S est rien de spécial mais un choisi au hasard le numéro.

Est-il un algorithme efficace d'autres que la force brutale de recherche pour trouver trois nombres entiers?

Answer 1

Est-il un algorithme efficace d'autres que la force brutale de recherche pour trouver trois nombres entiers?

Yep; nous pouvons le résoudre en O(n²) temps! Tout d'abord, considérez votre problème P peut être formulée de manière équivalente, de manière un peu différente, ce qui élimine la nécessité d'une "valeur cible":

problème d'origine P: étant Donné un tableau A de n des entiers et une valeur cible S, existe-t-il une 3-tuple de A qui sommes à l' S?

modifié problème P': étant Donné un tableau A de n des entiers, existe-t-il une 3-tuple de A qui sommes à zéro?

Notez que vous pouvez aller à partir de cette version du problème, P' de P en soustrayant votre S/3 de chaque élément en A, mais maintenant, vous n'avez pas besoin de la valeur cible plus.

Clairement, si on se contente de tester tous les possibles 3-n-uplets, nous aimerions résoudre le problème en O(n³)- c'est la force brute de base. Est-il possible de faire mieux? Si nous choisissons le tuples dans un peu plus intelligemment?

Tout d'abord, nous investir un peu de temps pour trier le tableau, qui nous coûte une pénalité initiale de O(n log n). Maintenant on exécute cet algorithme:

for (i in 1..n-2) {
  j = i+1  // Start right after i.
  k = n    // Start at the end of the array.

  while (k >= j) {
    // We got a match! All done.
    if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])

    // We didn't match. Let's try to get a little closer:
    //   If the sum was too big, decrement k.
    //   If the sum was too small, increment j.
    (A[i] + A[j] + A[k] > 0) ? k-- : j++
  }
  // When the while-loop finishes, j and k have passed each other and there's
  // no more useful combinations that we can try with this i.
}

Cet algorithme fonctionne en plaçant trois pointeurs, i, j, et k , à différents points dans le tableau. i commence au début et lentement fait son chemin à la fin. k points au dernier élément. j de points à l'endroit où i a commencé à. Nous itérative essayer de faire la somme des éléments à leurs indices respectifs, et chaque fois que l'un des cas suivants:

• La somme est exactement ça! Nous avons trouvé la réponse.
• La somme était trop petite. Déplacer j plus près de la fin pour sélectionner le prochain plus grand nombre.
• La somme était trop grand. Déplacer k plus près du début de sélectionner le prochain plus petit nombre.

Pour chaque i, les pointeurs de j et k va progressivement se rapprocher les uns des autres. Finalement, ils vont passer les uns des autres, et à ce moment, nous n'avons pas besoin d'essayer quoi que ce soit, i, puisque nous serions en additionnant les mêmes éléments, juste dans un ordre différent. Après ce point, nous essayons le prochain i et répétez.

Finalement, nous allons soit épuiser les possibilités, ou nous allons trouver la solution. Vous pouvez voir que ce est O(n²) puisque l'on execute la boucle externe O(n) fois et on exécute la boucle interne O(n) fois. Il est possible de le faire sous-quadratiquement si vous avez vraiment de fantaisie, en représentant chaque entier comme un vecteur de bits et d'effectuer une transformée de Fourier rapide, mais c'est au-delà de la portée de cette réponse.

---

Remarque: Parce que c'est une question d'entrevue, j'ai triché un peu ici: cet algorithme permet la sélection de la même élément plusieurs fois. Qui est, (-1, -1, 2), serait une solution valide, comme le ferait (0, 0, 0). Elle aussi trouve que l' exacte des réponses, pas la réponse la plus exacte, comme le titre le mentionne. Comme exercice pour le lecteur, je vais vous le trouver comment le faire fonctionner avec des éléments distincts seulement (mais c'est un très simple changement) et des réponses exactes (qui est aussi un simple changement).

Answer 2

ce n’est certainement une meilleure solution car il est plus facile à lire et donc moins sujette aux erreurs. Le seul problème est, il faut ajouter quelques lignes de code pour éviter la sélection multiple d’un seul élément.

Une autre solution de O(n^2) (en utilisant un hashset).

Answer 3

Solution de John Feminella a un bug.

À la ligne

Nous devons vérifier si i, j, k sont toutes distinctes. Sinon, si mon élément cible est et si mon tableau d’entrée contient . Si j’ai imprimer les tuples cette somme de 6, je recevrais aussi `` comme sortie. Pour éviter cela, nous avons besoin de modifier la condition de cette façon.

Answer 4

Que diriez-vous quelque chose comme ce qui est O(n^2)

Ceci conclut que si la somme des 3 éléments est exactement égale à votre nombre. Si vous voulez plus proche de vous, vous pouvez le modifier pour n’oubliez pas le plus petit delta (différence entre votre nombre de triplet actuel) et à la fin d’impression du triplet correspondant à delta plus petit.

Answer 5

Notez que nous avons un tableau trié. Cette solution est similaire à Jean uniquement à la solution qu'il recherche la somme et de ne pas répéter le même élément

#include <stdio.h>


int checkForSum (int arr[], int len, int somme) { //arr est trié


 int i;
 for (i = 0; i < len ; i++) {
 int gauche = i + 1;
 int droite = len - 1;

 alors que (à droite > gauche) {

 printf ("les valeurs sont %d %d %d\n", arr[i], arr[à gauche], arr[droite]);
 si (arr[droit] + arr[gauche] + arr[i] - somme == 0) {
 printf ("les valeurs finales sont %d %d %d\n", arr[i], arr[à gauche], arr[droite]);
 return 1;
}
 si (arr[droit] + arr[gauche] + arr[i] - somme > 0)
droit--;
d'autre
gauche++;

}

}
 return -1;
}




int main (int argc, char **argv) {

 int arr[] = {-99, -45, -6, -5, 0, 9, 12, 16, 21, 29};
 int somme = 4;
 printf ("vérifier la somme de %d arr est %d\n", somme, checkForSum(arr, 10, somme));


}