Encontrar tres elementos en una matriz cuya sum es la más cercana a un número determinado

Dado un conjunto de enteros, A 1 , A 2 , …, A n , incluidos los negativos y positivos, y otro entero S. Ahora tenemos que encontrar tres enteros diferentes en la matriz, cuya sum es más cercana al número entero dado S . Si existe más de una solución, cualquiera de ellas está bien.

Puede suponer que todos los enteros están dentro del rango int32_t, y no se producirá ningún desbordamiento aritmético al calcular la sum. S no es nada especial, sino un número elegido al azar.

¿Hay algún algoritmo eficiente que no sea la búsqueda de fuerza bruta para encontrar los tres enteros?

¿Hay algún algoritmo eficiente que no sea la búsqueda de fuerza bruta para encontrar los tres enteros?

Sí; ¡podemos resolver esto en el tiempo O (n 2 )! En primer lugar, considere que su problema P puede redactarse de manera equivalente de una manera ligeramente diferente que elimina la necesidad de un “valor objective”:

problema original P : dada una matriz A de n enteros y un valor objective S , ¿existe una 3-tupla de A que sum a S ?

problema modificado P' : dada una matriz A de n enteros, ¿existe una 3-tupla de A que sum cero?

Observe que puede pasar de esta versión del problema P' de P al restar su S / 3 de cada elemento en A , pero ahora ya no necesita el valor objective.

Claramente, si simplemente probamos todas las 3-tuplas posibles, resolveremos el problema en O (n 3 ) – esa es la línea base de fuerza bruta. ¿Es posible hacerlo mejor? ¿Qué pasa si escogemos las tuplas de una manera algo más inteligente?

Primero, invertimos algo de tiempo para ordenar la matriz, lo que nos cuesta una penalización inicial de O (n log n). Ahora ejecutamos este algoritmo:

 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. } 

Este algoritmo funciona colocando tres punteros, i , j en varios puntos de la matriz. Empiezo al principio y poco a poco avanzo hasta el final. k apunta al último elemento. j apunta a donde comencé. Tratamos iterativamente de sumr los elementos en sus índices respectivos, y cada vez sucede lo siguiente:

  • ¡La sum es exactamente correcta! Hemos encontrado la respuesta.
  • La sum fue muy pequeña. Mueva j más cerca del final para seleccionar el siguiente número más grande.
  • La sum fue muy grande. Acerque k al comienzo para seleccionar el siguiente número más pequeño.

Para cada i , los punteros de j y k se acercarán gradualmente el uno al otro. Eventualmente se pasarán el uno al otro, y en ese punto no necesitamos probar nada más para eso, ya que estaríamos sumndo los mismos elementos, solo que en un orden diferente. Después de ese punto, probamos el siguiente i y repito.

Eventualmente, agotaremos las posibilidades útiles o encontraremos la solución. Puedes ver que esto es O (n 2 ) ya que ejecutamos el ciclo externo O (n) veces y ejecutamos el ciclo interno O (n) veces. Es posible hacer esto sub-cuadráticamente si te apetece realmente, al representar cada entero como un vector de bits y realizar una transformada de Fourier rápida, pero eso está más allá del scope de esta respuesta.


Nota: Debido a que esta es una pregunta de la entrevista, he hecho trampa un poco aquí: este algoritmo permite la selección del mismo elemento varias veces. Es decir, (-1, -1, 2) sería una solución válida, al igual que (0, 0, 0). También encuentra solo las respuestas exactas , no la respuesta más cercana, como el título menciona. Como ejercicio para el lector, le dejaré descubrir cómo hacerlo funcionar solo con elementos distintos (pero es un cambio muy simple) y respuestas exactas (que también es un cambio simple).

ciertamente esta es una mejor solución porque es más fácil de leer y, por lo tanto, menos propensa a errores. El único problema es que necesitamos agregar algunas líneas de código para evitar la selección múltiple de un elemento.

Otra solución O (n ^ 2) (usando 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]) 

¿Qué tal algo así, que es 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. } } 

Esto se encuentra si la sum de 3 elementos es exactamente igual a su número. Si quiere más cercano, puede modificarlo para recordar el delta más pequeño (diferencia entre su número de triplete actual) y al final imprimir el triplete correspondiente al delta más pequeño.

La solución de John Feminella tiene un error.

En la línea

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

Necesitamos verificar si i, j, k son todos distintos. De lo contrario, si mi elemento objective es 6 y si mi matriz de entrada contiene {3,2,1,7,9,0,-4,6} . Si 0,0,6 las tuplas que sumn 6, también obtendré 0,0,6 como resultado. Para evitar esto, necesitamos modificar la condición de esta manera.

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

Tenga en cuenta que tenemos una matriz ordenada. Esta solución es similar a la solución de John solo que busca la sum y no repite el mismo elemento.

 #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)); } 

Aquí está el código de 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; } 

Solución N2 2 * logN muy simple: clasifique la matriz de entrada, luego pase por todos los pares A i , A j (N ^ 2 veces), y para cada par verifique si (S – A i – A j ) está en la matriz ( tiempo logN).

Otra solución O (S * N) utiliza un enfoque de progtwigción dinámica clásica.

En breve:

Cree una matriz de 2 d V [4] [S + 1]. Llénalo de tal manera, que:

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

V 1 [A i ] = 1 para cualquier i, V 1 [x] = 0 para todas las demás x

V [2] [A i + A j ] = 1, para cualquier i, j. V [2] [x] = 0 para todas las demás x

V [3] [sum de 3 elementos] = 1.

Para llenarlo, itere a través de A i , para cada Ai itere a través de la matriz de derecha a izquierda.

Esto se puede resolver de manera eficiente en O (n log (n)) de la siguiente manera. Estoy dando una solución que dice si la sum de tres números es igual a un número dado.

 import java.util.*; public class MainClass { public static void main(String[] args) { int[] a = {-1, 0, 1, 2, 3, 5, -4, 6}; System.out.println(((Object) isThreeSumEqualsTarget(a, 11)).toString()); } public static boolean isThreeSumEqualsTarget(int[] array, int targetNumber) { //O(n log (n)) Arrays.sort(array); System.out.println(Arrays.toString(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; } } 

Reducción: creo que la solución de John Feminella O (n2) es más elegante. Todavía podemos reducir el A [n] en el que buscar tupla. Al observar A [k] tal que todos los elementos estarían en A [0] – A [k], cuando nuestra matriz de búsqueda es enorme y SUM (s) realmente pequeña.

A [0] es mínimo: – Arreglo ordenado ascendente.

s = 2A [0] + A [k]: dados s y A [] podemos encontrar A [k] utilizando la búsqueda binaria en tiempo log (n).

Otra solución que verifica y falla temprano:

 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; } 

Agregué algunas pruebas unitarias aquí: GivenArrayReturnTrueIfThreeElementsSumZeroTest .

Si el conjunto usa demasiado espacio, puedo usar fácilmente un java.util.BitSet que usará O (n / w) espacio .

Aquí está el progtwig en Java que es 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) { StringBuilder sb = new StringBuilder(); sb.append(TARGET_SUM).append(" = "); for (Integer i : stack) { sb.append(i).append("+"); } System.out.println(sb.deleteCharAt(sb.length() - 1).toString()); } private static final int[] DATA = {4,13,14,15,17}; public static void main(String[] args) { GetAllSubsetByStack get = new GetAllSubsetByStack(); get.populateSubset(DATA, 0, DATA.length); } } 

El problema se puede resolver en O (n ^ 2) extendiendo el problema de sum de dos con modificaciones menores. A es el vector que contiene elementos y B es la sum requerida.

int Solución :: 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 

Hice esto en n ^ 3, mi pseudocódigo está abajo;

// Crea un hashMap con la clave como Integer y el valor como ArrayList // itera a través de la lista usando un ciclo for, para cada valor en la lista itera nuevamente comenzando desde el siguiente valor;

 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] y arr [j] es menor que la sum deseada, entonces existe la posibilidad de encontrar un tercer dígito, así que haga otro para el ciclo

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

// en este caso, ahora estamos buscando el tercer valor; si la sum de arr [i] y arr [j] y arr [k] es la sum deseada, agréguela al HashMap haciendo la clave arr [i] y luego agregando arr [j] y arr [k] en ArrayList en el valor de esa clave

  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]);} 

después de esto, ahora tiene un diccionario que tiene todas las entradas que representan los tres valores que se sumn a la sum deseada. Extraiga todas estas entradas usando las funciones de HashMap. Esto funcionó perfectamente.