Recherche de trois éléments dans un tableau dont la sum est la plus proche d’un nombre donné

Étant donné un tableau d’entiers, A 1 , A 2 , …, A n , y compris les négatifs et les positifs, et un autre entier S. Maintenant, nous devons trouver trois entiers différents dans le tableau, dont la sum est la plus proche de l’entier S S’il existe plusieurs solutions, l’une d’elles est correcte.

Vous pouvez supposer que tous les nombres entiers sont compris dans l’intervalle int32_t et qu’aucun calcul arithmétique ne se produira lors du calcul de la sum. S n’est rien de spécial mais un nombre choisi au hasard.

Existe-t-il un algorithme efficace autre que la recherche par force brute pour trouver les trois nombres entiers?

Existe-t-il un algorithme efficace autre que la recherche par force brute pour trouver les trois nombres entiers?

Oui; nous pouvons résoudre ce problème en O (n 2 ) temps! Tout d’abord, considérez que votre problème P peut être formulé de manière équivalente d’une manière légèrement différente, ce qui élimine le besoin d’une “valeur cible”:

problème original P : Étant donné un tableau A de n nombres entiers et une valeur cible S , existe-t-il un sortingplet de A qui sum à S ?

modified problem P' : Étant donné un tableau A de n entiers, existe-t-il un 3-tuple de A qui est nul?

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

De toute évidence, si nous testons simplement tous les 3-tuples possibles, nous résoudrions le problème dans O (n 3 ) – c’est la ligne de base de la force brute. Est-il possible de faire mieux? Et si nous sélectionnons les tuples de manière plus intelligente?

Tout d’abord, nous investissons un peu de temps pour sortinger le tableau, ce qui nous coûte une pénalité initiale de O (n log n). Maintenant, nous exécutons 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 du tableau. i commence au début et travaille lentement jusqu’à la fin. k pointe vers le tout dernier élément. j pointe vers où i commencé. Nous essayons itérativement de résumer les éléments à leurs indices respectifs, et à chaque fois que l’un des événements suivants se produit:

  • La sum est exacte! Nous avons trouvé la réponse.
  • La sum était trop petite. Rapprochez-vous de la fin pour sélectionner le plus grand nombre suivant.
  • La sum était trop grande. Rapprochez-vous du début pour sélectionner le plus petit nombre suivant.

Pour chaque i , les pointeurs de j et de k se rapprochent progressivement. Ils finiront par se croiser et, à ce moment-là, nous n’avons pas besoin d’essayer autre chose, car nous additionnerions les mêmes éléments, dans un ordre différent. Après ce point, nous essayons le prochain i et répétons.

Finalement, nous allons soit épuiser les possibilités utiles, soit trouver la solution. Vous pouvez voir que c’est O (n 2 ) puisque nous exécutons la boucle externe O (n) fois et que nous exécutons la boucle interne O (n) fois. Il est possible de faire cela sub-quadratiquement si vous avez vraiment envie, en représentant chaque entier comme un vecteur de bits et en effectuant une transformation de Fourier rapide, mais cela dépasse le cadre de cette réponse.


Note: Comme il s’agit d’une question d’entretien, j’ai un peu sortingché ici: cet algorithme permet de sélectionner plusieurs fois le même élément. C’est-à-dire que (-1, -1, 2) serait une solution valide, comme le ferait (0, 0, 0). Il ne trouve également que les réponses exactes , pas la réponse la plus proche, comme le mentionne le titre. En guise d’exercice pour le lecteur, je vous laisse découvrir comment le faire fonctionner uniquement avec des éléments distincts (mais c’est un changement très simple) et des réponses exactes (ce qui est aussi un simple changement).

c’est certainement une meilleure solution car elle est plus facile à lire et donc moins sujette aux erreurs. Le seul problème est que nous devons append quelques lignes de code pour éviter la sélection multiple d’un élément.

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

 // K is the sum that we are looking for for i 1..n int s1 = K - A[i] for j 1..i int s2 = s1 - A[j] if (set.contains(s2)) print the numbers set.add(A[i]) 

Que diriez-vous de quelque chose comme ceci, qui est O (n ^ 2)

 for(each ele in the sorted array) { ele = arr[i] - YOUR_NUMBER; let front be the pointer to the front of the array; let rear be the pointer to the rear element of the array.; // till front is not greater than rear. while(front <= rear) { if(*front + *rear == ele) { print "Found triplet "<<*front<<","<<*rear<<","< ele, so we need to decrease the sum by decrementing rear pointer. if((*front + *rear) > ele) decrement rear pointer. // sum is < ele, so we need to increase the sum by incrementing the front pointer. else increment front pointer. } } 

Cela trouve si la sum de 3 éléments est exactement égale à votre nombre. Si vous voulez le plus proche, vous pouvez le modifier pour mémoriser le plus petit delta (différence entre votre numéro de sortingplet actuel) et à la fin, imprimer le sortingplet correspondant au plus petit delta.

La solution de John Feminella a un bug.

À la ligne

 if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k]) 

Nous devons vérifier si i, j, k sont tous distincts. Sinon, si mon élément cible est 6 et si mon tableau d’entrée contient {3,2,1,7,9,0,-4,6} . Si 0,0,6 les tuples qui 0,0,6 6, alors j’obtiendrais également 0,0,6 en sortie. Pour éviter cela, nous devons modifier la condition de cette manière.

 if ((A[i] + A[j] + A[k] == 0) && (i!=j) && (i!=k) && (j!=k)) return (A[i], A[j], A[k]) 

Notez que nous avons un tableau sortingé. Cette solution est similaire à la solution de John, mais elle recherche uniquement la sum et ne répète pas le même élément.

 #include ; int checkForSum (int arr[], int len, int sum) { //arr is sorted int i; for (i = 0; i < len ; i++) { int left = i + 1; int right = len - 1; while (right > left) { printf ("values are %d %d %d\n", arr[i], arr[left], arr[right]); if (arr[right] + arr[left] + arr[i] - sum == 0) { printf ("final values are %d %d %d\n", arr[i], arr[left], arr[right]); return 1; } if (arr[right] + arr[left] + arr[i] - sum > 0) right--; else left++; } } return -1; } int main (int argc, char **argv) { int arr[] = {-99, -45, -6, -5, 0, 9, 12, 16, 21, 29}; int sum = 4; printf ("check for sum %d in arr is %d\n", sum, checkForSum(arr, 10, sum)); } 

Voici le code C ++:

 bool FindSumZero(int a[], int n, int& x, int& y, int& z) { if (n < 3) return false; sort(a, a+n); for (int i = 0; i < n-2; ++i) { int j = i+1; int k = n-1; while (k >= j) { int s = a[i]+a[j]+a[k]; if (s == 0 && i != j && j != k && k != i) { x = a[i], y = a[j], z = a[k]; return true; } if (s > 0) --k; else ++j; } } return false; } 

Très simple solution N ^ 2 * logN: sortingez le tableau d’entrée, puis parcourez toutes les paires A i , A j (N ^ 2 time), et pour chaque paire, vérifiez si (S – A i – A j ) est dans le tableau ( logN time).

Une autre solution O (S * N) utilise une approche de programmation dynamic classique.

En bref:

Créez un tableau à deux dimensions V [4] [S + 1]. Remplissez-le de telle manière que:

V [0] [0] = 1, V [0] [x] = 0;

V 1 [A i ] = 1 pour tout i, V 1 [x] = 0 pour tous les autres x

V [2] [A i + A j ] = 1, pour tout i, j. V [2] [x] = 0 pour tous les autres x

V [3] [sum de 3 éléments] = 1.

Pour le remplir, parcourez A i , pour chaque A, parcourez le tableau de droite à gauche.

Cela peut être résolu efficacement dans O (n log (n)) comme suit. Je donne une solution qui indique si la sum de trois nombres est égale à un nombre donné.

 import java.util.*; public class MainClass { public static void main(Ssortingng[] args) { int[] a = {-1, 0, 1, 2, 3, 5, -4, 6}; System.out.println(((Object) isThreeSumEqualsTarget(a, 11)).toSsortingng()); } public static boolean isThreeSumEqualsTarget(int[] array, int targetNumber) { //O(n log (n)) Arrays.sort(array); System.out.println(Arrays.toSsortingng(array)); int leftIndex = 0; int rightIndex = array.length - 1; //O(n) while (leftIndex + 1 < rightIndex - 1) { //take sum of two corners int sum = array[leftIndex] + array[rightIndex]; //find if the number matches exactly. Or get the closest match. //here i am not storing closest matches. You can do it for yourself. //O(log (n)) complexity int binarySearchClosestIndex = binarySearch(leftIndex + 1, rightIndex - 1, targetNumber - sum, array); //if exact match is found, we already got the answer if (-1 == binarySearchClosestIndex) { System.out.println(("combo is " + array[leftIndex] + ", " + array[rightIndex] + ", " + (targetNumber - sum))); return true; } //if exact match is not found, we have to decide which pointer, left or right to move inwards //we are here means , either we are on left end or on right end else { //we ended up searching towards start of array,ie we need a lesser sum , lets move inwards from right //we need to have a lower sum, lets decrease right index if (binarySearchClosestIndex == leftIndex + 1) { rightIndex--; } else if (binarySearchClosestIndex == rightIndex - 1) { //we need to have a higher sum, lets decrease right index leftIndex++; } } } return false; } public static int binarySearch(int start, int end, int elem, int[] array) { int mid = 0; while (start <= end) { mid = (start + end) >>> 1; if (elem < array[mid]) { end = mid - 1; } else if (elem > array[mid]) { start = mid + 1; } else { //exact match case //Suits more for this particular case to return -1 return -1; } } return mid; } } 

Réduction: Je pense que la solution @John Feminella O (n2) est la plus élégante. On peut encore réduire le A [n] dans lequel chercher le tuple. En observant A [k] tel que tous les éléments seraient dans A [0] – A [k], lorsque notre tableau de recherche est énorme et que SUM (s) est vraiment petit.

Un [0] est minimum: – tableau sortingé croissant.

s = 2A [0] + A [k]: Avec s et A [] on peut trouver A [k] en utilisant la recherche binary dans le log (n) time.

Une autre solution qui vérifie et échoue tôt:

 public boolean solution(int[] input) { int length = input.length; if (length < 3) { return false; } // x + y + z = 0 => -z = x + y final Set z = new HashSet<>(length); int zeroCounter = 0, sum; // if they're more than 3 zeros we're done for (int element : input) { if (element < 0) { z.add(element); } if (element == 0) { ++zeroCounter; if (zeroCounter >= 3) { return true; } } } if (z.isEmpty() || z.size() == length || (z.size() + zeroCounter == length)) { return false; } else { for (int x = 0; x < length; ++x) { for (int y = x + 1; y < length; ++y) { sum = input[x] + input[y]; // will use it as inverse addition if (sum < 0) { continue; } if (z.contains(sum * -1)) { return true; } } } } return false; } 

J'ai ajouté des tests unitaires ici: GivenArrayReturnTrueIfThreeElementsSumZeroTest .

Si l'ensemble utilise trop d'espace, je peux facilement utiliser un java.util.BitSet qui utilisera un espace O (n / w).

Voici le programme en Java qui est O (N ^ 2)

 import java.util.Stack; public class GetTripletPair { /** Set a value for target sum */ public static final int TARGET_SUM = 32; private Stack stack = new Stack(); /** Store the sum of current elements stored in stack */ private int sumInStack = 0; private int count =0 ; public void populateSubset(int[] data, int fromIndex, int endIndex) { /* * Check if sum of elements stored in Stack is equal to the expected * target sum. * * If so, call print method to print the candidate satisfied result. */ if (sumInStack == TARGET_SUM) { print(stack); } for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) { if (sumInStack + data[currentIndex] <= TARGET_SUM) { ++count; stack.push(data[currentIndex]); sumInStack += data[currentIndex]; /* * Make the currentIndex +1, and then use recursion to proceed * further. */ populateSubset(data, currentIndex + 1, endIndex); --count; sumInStack -= (Integer) stack.pop(); }else{ return; } } } /** * Print satisfied result. ie 15 = 4+6+5 */ private void print(Stack stack) { SsortingngBuilder sb = new SsortingngBuilder(); sb.append(TARGET_SUM).append(" = "); for (Integer i : stack) { sb.append(i).append("+"); } System.out.println(sb.deleteCharAt(sb.length() - 1).toSsortingng()); } private static final int[] DATA = {4,13,14,15,17}; public static void main(Ssortingng[] args) { GetAllSubsetByStack get = new GetAllSubsetByStack(); get.populateSubset(DATA, 0, DATA.length); } } 

Le problème peut être résolu en O (n ^ 2) en étendant le problème à 2 sum avec des modifications mineures. A est le vecteur contenant les éléments et B la sum requirejse.

int Solution :: threeSumClosest (vector & A, int B) {

 sort(A.begin(),A.end()); int k=0,i,j,closest,val;int diff=INT_MAX; while(kval) ++i; if(B 

Je l’ai fait en n ^ 3, mon pseudocode est en dessous;

// Crée un hashMap avec la clé Integer et la valeur ArrayList // itère dans la liste en utilisant une boucle for, pour chaque valeur de la liste iterate à partir de la valeur suivante;

 for (int i=0; i<=arr.length-1 ; i++){ for (int j=i+1; j<=arr.length-1;j++){ 

// si la sum de arr [i] et arr [j] est inférieure à la sum souhaitée, il est possible de trouver un troisième chiffre, alors faites une autre pour la boucle

  if (arr[i]+arr[j] < sum){ for (int k= j+1; k<=arr.length-1;k++) 

// dans ce cas nous recherchons maintenant la troisième valeur; si la sum de arr [i] et arr [j] et arr [k] est la sum désirée, ajoutez-les à HashMap en effectuant l'arr [i] la clé puis en ajoutant arr [j] et arr [k] dans le ArrayList dans la valeur de cette clé

  if (arr[i]+arr[j]+arr[k] == sum){ map.put(arr[i],new ArrayList()); map.get(arr[i]).add(arr[j]); map.get(arr[i]).add(arr[k]);} 

après cela, vous avez maintenant un dictionnaire qui contient toutes les entrées représentant les trois valeurs, en ajoutant à la sum souhaitée. Extrayez toutes ces entrées en utilisant les fonctions HashMap. Cela a parfaitement fonctionné.