Encontrar tres elementos en una matriz cuya suma sea la más cercana a un número dado

¿Existe algún algoritmo eficiente además de la búsqueda de fuerza bruta para encontrar los tres números enteros?

Sí; ¡ Podemos resolver esto en tiempo O(n ^{2 )!} Primero, considere que su problema Pse puede formular de manera equivalente de una manera ligeramente diferente que elimine la necesidad de un "valor objetivo":

Problema original P: dada una matriz Ade nnúmeros enteros y un valor objetivo S, ¿existe una tupla de 3 Aque sume S?

Problema modificado P': Dada una matriz Ade nnúmeros enteros, ¿existe una tupla de 3 Aque suma hasta cero?

Tenga en cuenta que puede pasar de esta versión del problema P'restando Psu S/3 de cada elemento en A, pero ahora ya no necesita el valor objetivo.

Claramente, si simplemente probamos todas las 3-tuplas posibles, resolveríamos el problema en O(n ³ ), esa es la línea de base de la fuerza bruta. ¿Es posible hacerlo mejor? ¿Qué pasa si elegimos 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, jy ken varios puntos de la matriz. icomienza desde el principio y poco a poco avanza hasta el final. kapunta al último elemento. jseñala dónde icomenzó. Intentamos iterativamente sumar los elementos en sus respectivos índices, y cada vez ocurre una de las siguientes situaciones:

• ¡La suma es exactamente correcta! Hemos encontrado la respuesta.
• La suma era demasiado pequeña. Acércate jal final para seleccionar el siguiente número más grande.
• La suma era demasiado grande. Acérquese kal principio para seleccionar el siguiente número más pequeño.

Para cada uno i, los punteros de jy kse acercarán gradualmente entre sí. Eventualmente se cruzarán, y en ese punto no necesitamos intentar nada más para eso i, ya que estaríamos sumando los mismos elementos, solo que en un orden diferente. Pasado ese punto, probamos el siguiente iy repetimos.

Con el tiempo, agotaremos las posibilidades útiles o encontraremos la solución. Puede ver que esto es O(n ² ) ya que ejecutamos el bucle externo O(n) veces y ejecutamos el bucle interno O(n) veces. Es posible hacer esto subcuadráticamente si te pones realmente elegante, representando cada número entero como un vector de bits y realizando una transformada rápida de Fourier, pero eso está más allá del alcance de esta respuesta.

Nota: Como se trata de una pregunta de una entrevista, he hecho un poco de trampa 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 sólo las respuestas exactas , no la respuesta más cercana, como menciona el título. Como ejercicio para el lector, le dejaré descubrir cómo hacer que funcione solo con elementos distintos (pero es un cambio muy simple) y respuestas exactas (que también es un cambio simple).

Jan 15 '2010 09:01 John Feminella