encontrar un par de números en el conjunto que se sumn a la sum dada

Pregunta: Dado un conjunto desordenado de enteros positivos, ¿es posible encontrar un par de enteros de ese conjunto que sumen una sum determinada?

Restricciones: Esto debe hacerse en O (n) y en contexto (sin ningún tipo de almacenamiento externo como arreglos, hash-maps) (puede usar variables / punteros adicionales)

Si esto no es posible, ¿puede haber una prueba para el mismo?

Si tiene una matriz ordenada, puede encontrar dicha pareja en O (n) moviendo dos punteros hacia la mitad

 i = 0 j = n-1 while(i < j){ if (a[i] + a[j] == target) return (i, j); else if (a[i] + a[j] < target) i += 1; else if (a[i] + a[j] > target) j -= 1; } return NOT_FOUND; 

La clasificación se puede hacer O (N) si tiene un límite en el tamaño de los números (o si la matriz ya está ordenada en primer lugar). Incluso entonces, un factor de inicio de sesión n es realmente pequeño y no quiero molestarme en afeitarlo.

prueba:

Si hay una solución (i*, j*) , supongamos, sin pérdida de generalidad, que alcanzo i* antes de que j scope j* . Dado que para todo j' entre j* y j sabemos que a[j'] > a[j*] podemos extrapolar que a[i] + a[j'] > a[i*] + a[j*] = target y, por lo tanto, que todos los siguientes pasos del algoritmo harán que j disminuya hasta que scope j* (o un valor igual) sin darme la oportunidad de avanzar y “perder” la solución.

La interpretación en la otra dirección es similar.

Una solución de espacio O(N) y O(1) que funciona en una matriz ordenada:

Deje que M sea ​​el valor que busca. Use dos punteros, X e Y Comience X=0 al comienzo e Y=N-1 al final. Calcule la sum sum = array[X] + array[Y] . Si sum > M , entonces disminuya Y , de lo contrario, incremente X Si los punteros se cruzan, entonces no existe solución.

Puede ordenar en su lugar para obtener esto para una matriz general, pero no estoy seguro de que haya una solución espacial O(N) y O(1) en general.

Esto podría ser posible si la matriz contiene números, cuyo límite superior conoce de antemano. A continuación, utilice la clase de recuento o ordenación de radix (o (n)) y utilice el algoritmo que sugirió @PengOne.

De lo contrario, no puedo pensar en la solución O (n). Pero la solución O (nlgn) funciona de esta manera: –

Primero ordena la matriz usando el tipo de fusión o clasificación rápida (para inplace). Encuentra si sum – array_element está en esta matriz ordenada. Uno puede usar la búsqueda binaria para eso.

 So total time complexity: O(nlgn) + O(lgn) -> O(nlgn). 

AS @PengOne mencionó que no es posible en el esquema general de las cosas. Pero si haces algunas restricciones en los datos de i / p.

  1. todos los elementos son todos + o todos -, si no, necesitaría conocer el rango (alto, bajo) y los cambios realizados.
  2. K, la sum de dos enteros es escasa en comparación con los elementos en general.
  3. Está bien destruir la matriz i / p A [N].

Paso 1: Mueva todos los elementos inferiores a SUM al comienzo de la matriz; por ejemplo, en N Passes, hemos dividido la matriz en [0, K] y [K, N-1] de manera que [0, K] contenga elementos < = SUMA.

Paso 2: dado que conocemos los límites (0 a SUM) podemos usar el orden de radix.

Paso 3: utilice la búsqueda binaria en A [K], una cosa buena es que si necesitamos encontrar un elemento complementario, solo necesitamos ver la mitad de la matriz A [K]. entonces en A [k] iteramos sobre A [0 a K / 2 + 1] tenemos que hacer una búsqueda binaria en A [i a K].

Tan total appx. el tiempo es, N + K + K / 2 lg (K) donde K es el número de elementos por cierto 0 a Suma en i / p A [N]

Nota: si usas el enfoque de @ PengOne puedes hacer el paso 3 en K. Así que el tiempo total sería N + 2K, que es definitivamente O (N)

No usamos ninguna memoria adicional, pero destruimos la matriz i / p, que tampoco está mal, ya que no tenía ningún orden para empezar.

Primero, ordena la matriz usando radix sort . Eso te hará retroceder O (kN). Luego proceda como sugiere @PengOne.

El siguiente sitio proporciona una solución simple usando hashset que ve un número y luego busca en el hashset el número sum-current dado http://www.dsalgo.com/UnsortedTwoSumToK.php

Aquí hay un algoritmo O (N). Se basa en un algoritmo de eliminación de duplicados en el lugar O (N) , y la existencia de una buena función hash para los ints en su matriz.

Primero, elimine todos los duplicados de la matriz.

Segundo, revise el conjunto y reemplace cada número x con min (x, Sx) donde S es la sum que desea alcanzar.

En tercer lugar, busque si hay duplicados en la matriz: si ‘x’ está duplicada, entonces ‘x’ y ‘Sx’ deben haber ocurrido en la matriz original, y ha encontrado su par.

Mi solución en Java (Complejidad del tiempo O (n)), esto generará todos los pares con una sum dada

 import java.util.HashMap; import java.util.Map; public class Test { public static void main(String[] args) { // TODO Auto-generated method stub Map hash = new HashMap<>(); int arr[] = {1,4,2,6,3,8,2,9}; int sum = 5; for (int i = 0; i < arr.length; i++) { hash.put(arr[i],i); } for (int i = 0; i < arr.length; i++) { if(hash.containsKey(sum-arr[i])){ System.out.println(i+ " " + hash.get(sum-arr[i])); } } } } 
  1. Use la clasificación de recuento para ordenar la matriz O (n).
  2. tomar dos punteros uno comienza desde el 0 ° índice de la matriz, y otro desde el final de la matriz decir (n-1).

    ejecutar el ciclo hasta que sea bajo < = alto

     Sum = arr[low] + arr[high] if(sum == target) print low, high if(sum < target) low++ if(sum > target) high-- 

    El paso 2 a 10 toma el tiempo de O (n), y la ordenación de conteo toma O (n). Entonces, la complejidad del tiempo total será O (n).

Aquí hay una solución que toma en cuenta las entradas duplicadas. Está escrito en javascript y se ejecuta con matrices ordenadas y no ordenadas. La solución se ejecuta en O (n) tiempo.

 var count_pairs_unsorted = function(_arr,x) { // setup variables var asc_arr = []; var len = _arr.length; if(!x) x = 0; var pairs = 0; var i = -1; var k = len-1; if(len<2) return pairs; // tally all the like numbers into buckets while(i-1){ var y; if(i1) { if(_arr[i]==y) { var comb = 1; while(--asc_arr[_arr[i]] > 0) {pairs+=(comb++);} } else pairs+=asc_arr[_arr[i]]*asc_arr[y]; asc_arr[y] = 0; asc_arr[_arr[i]] = 0; } } if(k>-1) { y = x-_arr[k]; if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[k]])>1) { if(_arr[k]==y) { var comb = 1; while(--asc_arr[_arr[k]] > 0) {pairs+=(comb++);} } else pairs+=asc_arr[_arr[k]]*asc_arr[y]; asc_arr[y] = 0; asc_arr[_arr[k]] = 0; } } i++; k--; } return pairs; } 

Comience en ambos lados de la matriz y avance lentamente hacia adentro, manteniendo un recuento de cuántas veces se encuentra cada número. Una vez que alcanzas el punto medio, todos los números son contados y ahora puedes avanzar ambos punteros contando los pares sobre la marcha.

Solo cuenta pares, pero se puede volver a trabajar para

  • encuentra los pares
  • encontrar pares
  • buscar pares> x

¡Disfrutar!

Implementación Ruby

 ar1 = [ 32, 44, 68, 54, 65, 43, 68, 46, 68, 56] for i in 0..ar1.length-1 t = 100 - ar1[i] if ar1.include?(t) s= ar1.count(t) if s < 2 print s , " - " , t, " , " , ar1[i] , " pair ", i, "\n" end end end 

En javascript: Este código cuando n es mayor que el tiempo y el número de iteraciones aumentan. El número de prueba realizado por el progtwig será igual a ((n * (n / 2) + n / 2) donde n es el número de elementos. El número de sum dado se descarta en if (arr [i] + arr [j ] === 0) donde 0 podría ser cualquier número dado.

 var arr = [-4, -3, 3, 4]; var lengtharr = arr.length; var i = 0; var j = 1; var k = 1; do { do { if (arr[i] + arr[j] === 0) { document.write(' Elements arr [' + i + '] [' + j + '] sum 0'); } else { document.write('____'); } j++; } while (j < lengtharr); k++; j = k; i++; } while (i < (lengtharr-1)); 

No garantizado que sea posible; ¿cómo se selecciona la sum dada?

Ejemplo: matriz sin clasificar de enteros

 2, 6, 4, 8, 12, 10 

Cantidad dada:

 7 

??

Aquí hay una solución en python:

 a = [9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 2, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 12, 2, 8, 9, 2, 15, 11, 21, 7, 9, 2, 23, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 12, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 7.12, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 0.87, 78] i = 0 j = len(a) - 1 my_sum = 8 finded_numbers = () iterations = 0 while(OK): iterations += 1 if (i < j): i += 1 if (i == j): if (i == 0): OK = False break i = 0 j -= 1 if (a[i] + a[j] == my_sum): finded_numbers = (a[i], a[j]) OK = False print finded_numbers print iterations 

Me hicieron esta misma pregunta durante una entrevista, y este es el plan que tenía en mente. Queda una mejora por hacer, para permitir números negativos, pero solo sería necesario modificar los índices. El espacio no es bueno, pero creo que el tiempo de ejecución aquí sería O (N) + O (N) + O (subconjunto de N) -> O (N). Puedo estar equivocado.

 void find_sum(int *array_numbers, int x){ int i, freq, n_numbers; int array_freq[x+1]= {0}; // x + 1 as there could be 0's as well if(array_numbers) { n_numbers = (int) sizeof(array_numbers); for(i=0; i 0)&&(array_freq[array_numbers[i]] > 0)&&(array_numbers[i]!=(x/2))) { freq = array_freq[x-array_numbers[i]] * array_freq[array_numbers[i]]; printf(“-{%d,%d} %d times\n”,array_numbers[i],x-array_numbers[i],freq ); // “-{3, 7} 6 times” if there's 3 '7's and 2 '3's array_freq[array_numbers[i]]=0; array_freq[x-array_numbers[i]]=0; // doing this we don't get them repeated } } // end loop if ((x%2)=0) { freq = array_freq[x/2]; n_numbers=0; for(i=1; i 

Los críticos son bienvenidos.

En Java, esto depende del número máximo en la matriz. devuelve un int [] que tiene los índices de dos elementos. está en).

  public static int[] twoSum(final int[] nums, int target) { int[] r = new int[2]; r[0] = -1; r[1] = -1; int[] vIndex = new int[0Xffff]; for (int i = 0; i < nums.length; i++) { int delta = 0Xfff; int gapIndex = target - nums[i] + delta; if (vIndex[gapIndex] != 0) { r[0] = vIndex[gapIndex]; r[1] = i + 1; return r; } else { vIndex[nums[i] + delta] = i + 1; } } return r; } 

Primero debes encontrar la matriz inversa => sum menos la matriz real y luego verificar si algún elemento de esta nueva matriz existe en la matriz real.

 const arr = [0, 1, 2, 6]; const sum = 8; let isPairExist = arr .map(item => sum - item) // [8, 7, 6, 2]; .find((item, index) => { arr.splice(0, 1); // an element should pair with another element return arr.find(x => x === item); }) ? true : false; console.log(isPairExist); 

La impresión ingenua de doble bucle con rendimiento O (nxn) puede mejorarse con el rendimiento O (n) lineal utilizando la memoria O (n) para la Tabla Hash de la siguiente manera:

 void TwoIntegersSum(int[] given, int sum) { Hashtable ht = new Hashtable(); for (int i = 0; i < given.Length; i++) if (ht.Contains(sum - given[i])) Console.WriteLine("{0} + {1}", given[i], sum - given[i]); else ht.Add(given[i], sum - given[i]); Console.Read(); } 
 def pair_sum(arr,k): counter = 0 lookup = set() for num in arr: if k-num in lookup: counter+=1 else: lookup.add(num) return counter pass pair_sum([1,3,2,2],4) 

La solución en python