O (NlogN) encontrar 3 números que tienen una suma de cualquier T arbitraria en una matriz

Question

Dada una matriz A de números enteros, encontrar cualquier 3 de ellos que sumar a cualquier dada T.

lo vi en alguna línea publicación, que afirma que tiene una solución O (NlogN).

Para 2 números, sé que hashtable podría ayudar para O (N), pero para 3 números, no puedo encontrar uno.

También creo que este problema suena familiar a algunos problemas difíciles, pero no puede recordar el nombre y, por lo tanto, no puede buscarlo en Google. (Mientras que lo peor es obviamente O (N^3), y con la solución a 2 números es realmente O (N^2))

Realmente no resuelve nada en el mundo real, solo me molesta ...

¿Alguna idea?

Answer 1

Creo que su problema es equivalente a la 3SUM problem.

Answer 2

Suena como una pregunta tarea ...

Si se pueden encontrar dos valores que suma a N pero que desea ampliar la búsqueda a tres valores, que no podía, para cada valor M en el conjunto, busque dos valores que suman (N - M)? Si puede encontrar dos valores que suman un valor específico en O (log N) time, entonces será O (N log N).

Answer 3

creo que esto es sólo el problema subset sum

Si es así, es NP-completo.

EDITAR: No importa, es 3sum, como se indica en otra respuesta.

Answer 4

2SUM problema puede resolverse en O (nlgn) tiempo.

Primero ordene la matriz que toma como máximo O (nlgn) operaciones. Ahora, en la iteración ith seleccionamos el elemento a[i] y encontramos el elemento -a[i] en la parte restante de la matriz (es decir, desde i+1 a n-1) y esta búsqueda podría realizarse en búsqueda binaria, lo que requiere como máximo tiempo de ignición. Entonces, en general, tomará operaciones O (nlgn).

Pero el problema 3SUM no se puede resolver en el tiempo O (nlgn). Podríamos reducirlo a O (n^2)

Answer 5

Para un problema de tres suma, no puede encontrar una solución mejor que O (n^2). Se puede hacer referencia a http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science

Answer 6

levantado directamente de https://en.wikipedia.org/wiki/3SUM

sort(S); 

    for i=0 to n-3 do 

     a = S[i]; 
     start = i+1; 

     end = n-1; 

     while (start < end) do 

      b = S[start]; 
      c = S[end]; 
      if (a+b+c == 0) then 
       output a, b, c; 
       // Continue search for all triplet combinations summing to zero. 
       start = start + 1 
       end = end - 1 

      else if (a+b+c > 0) then 
       end = end - 1; 
      else 
       start = start + 1; 
      end 
     end 
    end