Algoritmo de tiempo lineal para 2-SUM

Dado un número entero xy un conjunto ordenado a de N enteros distintos, diseñe un algoritmo de tiempo lineal para determinar si existen dos índices distintos i y j tales que a [i] + a [j] == x

Este es un tipo de problema de sum de subconjuntos

Aquí está mi solución. No sé si se supo antes o no. Imagine la representación 3D de la función de dos variables i y j:

sum(i,j) = a[i]+a[j] 

Para cada i existe tal j que a[i]+a[j] está más cerca de x . Todos estos pares (i,j) forman la línea más cercana a la x . Solo tenemos que caminar a lo largo de esta línea y buscar a[i]+a[j] == x :

  int i = 0; int j = lower_bound(a.begin(), a.end(), x) - a.begin(); while (j >= 0 && j < a.size() && i < a.size()) { int sum = a[i]+a[j]; if (sum == x) { cout << "found: " << i << " " << j << endl; return; } if (sum > x) j--; else i++; if (i > j) break; } cout << " not found\n"; 

Complejidad: O (n)

pensar en términos de complementos.

itere sobre la lista, determine para cada elemento cuál es el número necesario para llegar a X para ese número. número de palo y complemento en hash. mientras itera la comprobación para ver si el número o su complemento está en hash. si es así, encontrado.

editar: y como tengo algo de tiempo, algún código pseudo’ish.

 boolean find(int[] array, int x) { HashSet s = new HashSet(); for(int i = 0; i < array.length; i++) { if (s.contains(array[i]) || s.contains(x-array[i])) { return true; } s.add(array[i]); s.add(x-array[i]); } return false; } 
  1. La primera pasada busca el primer valor que sea> ceil (x / 2). Vamos a llamar a este valor L.
  2. Del índice de L, busca hacia atrás hasta que encuentres el otro operando que coincida con la sum.

Es 2 * n ~ O (n)

Esto podemos extenderlo a la búsqueda binaria.

  1. Busca un elemento usando la búsqueda binaria de manera que encontremos L, tal que L es min (elementos en a> ceil (x / 2)).

  2. Haga lo mismo para R, pero ahora con L como el tamaño máximo de elementos buscables en la matriz.

Este enfoque es 2 * log (n).

Aquí hay una versión de Python que utiliza la estructura de datos del diccionario y el complemento de números. Esto tiene un tiempo de ejecución lineal (orden de N: O (N)):

 def twoSum(N, x): dict = {} for i in range(len(N)): complement = x - N[i] if complement in dict: return True dict[N[i]] = i return False # Test print twoSum([2, 7, 11, 15], 9) # True print twoSum([2, 7, 11, 15], 3) # False 

Itera sobre la matriz y guarde los números calificados y sus índices en el mapa. La complejidad de tiempo de este algoritmo es O (n).

 vector twoSum(vector &numbers, int target) { map summap; vector result; for (int i = 0; i < numbers.size(); i++) { summap[numbers[i]] = i; } for (int i = 0; i < numbers.size(); i++) { int searched = target - numbers[i]; if (summap.find(searched) != summap.end()) { result.push_back(i + 1); result.push_back(summap[searched] + 1); break; } } return result; } 

Simplemente agregaría la diferencia a un HashSet así:

 public static bool Find(int[] array, int toReach) { HashSet hashSet = new HashSet(); foreach (int current in array) { if (hashSet.Contains(current)) { return true; } hashSet.Add(toReach - current); } return false; } 

Nota: El código es mío, pero el archivo de prueba no. Además, esta idea para la función hash proviene de varias lecturas en la red.

Una implementación en Scala. Utiliza un mapeo hashMap y un mapeo personalizado (aún simple) para los valores. Estoy de acuerdo en que no hace uso de la naturaleza ordenada de la matriz inicial.

La función hash

Arreglo el tamaño del cubo dividiendo cada valor entre 10000. Ese número puede variar, dependiendo del tamaño que desee para los depósitos, lo que puede hacerse óptimo dependiendo del rango de entrada.

Entonces, por ejemplo, la clave 1 es responsable de todos los enteros del 1 al 9.

Impacto en el scope de la búsqueda

Lo que eso significa es que para un valor actual n , para el que busca encontrar un complemento c , como n + c = x ( x es el elemento que está intentando encontrar una 2-SUM de), hay solo 3 segmentos posibles en los que el complemento puede ser:

  • -llave
  • -key + 1
  • -key – 1

Digamos que sus números están en un archivo de la siguiente forma:

 0 1 10 10 -10 10000 -10000 10001 9999 -10001 -9999 10000 5000 5000 -5000 -1 1000 2000 -1000 -2000 

Aquí está la implementación en Scala

 import scala.collection.mutable import scala.io.Source object TwoSumRed { val usage = """ Usage: scala TwoSumRed.scala [filename] """ def main(args: Array[String]) { val carte = createMap(args) match { case None => return case Some(m) => m } var t: Int = 1 carte.foreach { case (bucket, values) => { var toCheck: Array[Long] = Array[Long]() if (carte.contains(-bucket)) { toCheck = toCheck ++: carte(-bucket) } if (carte.contains(-bucket - 1)) { toCheck = toCheck ++: carte(-bucket - 1) } if (carte.contains(-bucket + 1)) { toCheck = toCheck ++: carte(-bucket + 1) } values.foreach { v => toCheck.foreach { c => if ((c + v) == t) { println(s"$c and $v forms a 2-sum for $t") return } } } } } } def createMap(args: Array[String]): Option[mutable.HashMap[Int, Array[Long]]] = { var carte: mutable.HashMap[Int,Array[Long]] = mutable.HashMap[Int,Array[Long]]() if (args.length == 1) { val filename = args.toList(0) val lines: List[Long] = Source.fromFile(filename).getLines().map(_.toLong).toList lines.foreach { l => val idx: Int = math.floor(l / 10000).toInt if (carte.contains(idx)) { carte(idx) = carte(idx) :+ l } else { carte += (idx -> Array[Long](l)) } } Some(carte) } else { println(usage) None } } } 
 int[] b = new int[N]; for (int i = 0; i < N; i++) { b[i] = x - a[N -1 - i]; } for (int i = 0, j = 0; i < N && j < N;) if(a[i] == b[j]) { cout << "found"; return; } else if(a[i] < b[j]) i++; else j++; cout << "not found"; 

Aquí hay una solución de complejidad de tiempo lineal O (n) tiempo O (1) espacio

  public void twoSum(int[] arr){ if(arr.length < 2) return; int max = arr[0] + arr[1]; int bigger = Math.max(arr[0], arr[1]); int smaller = Math.min(arr[0], arr[1]); int biggerIndex = 0; int smallerIndex = 0; for(int i = 2 ; i < arr.length ; i++){ if(arr[i] + bigger <= max){ continue;} else{ if(arr[i] > bigger){ smaller = bigger; bigger = arr[i]; biggerIndex = i; }else if(arr[i] > smaller) { smaller = arr[i]; smallerIndex = i; } max = bigger + smaller; } } System.out.println("Biggest sum is: " + max + "with indices ["+biggerIndex+","+smallerIndex+"]"); 

}

Solución

  • Necesitamos matriz para almacenar los índices
  • Compruebe si la matriz está vacía o contiene menos de 2 elementos
  • Definir el inicio y el punto final de la matriz
  • Itera hasta que se cumpla la condición
  • Verifica si la sum es igual al objective. Si es así, obtén los índices.
  • Si no se cumple la condición, recorra la izquierda o la derecha según el valor de la sum
  • Atravesar hacia la derecha
  • Atraviesa a la izquierda

Para más información: [ http://www.prathapkudupublog.com/2017/05/two-sum-ii-input-array-is-sorted.html enter image description here

Crédito a leonid

Su solución en Java, si quieres darle una oportunidad

Eliminé el retorno, por lo que si el conjunto está ordenado, pero permite duplicados, todavía da pares

 static boolean cpp(int[] a, int x) { int i = 0; int j = a.length - 1; while (j >= 0 && j < a.length && i < a.length) { int sum = a[i] + a[j]; if (sum == x) { System.out.printf("found %s, %s \n", i, j); // return true; } if (sum > x) j--; else i++; if (i > j) break; } System.out.println("not found"); return false; }