¿Se puede resolver el problema de 3SUM en tiempo subcuadrático?

El algoritmo que mencionó es fácil de implementar y no utiliza memoria adicional. Otra forma de resolverlo sería la siguiente:

1. Poner todos los valores de la matriz en un diccionario
2. Genere todos los pares de valores en la matriz de entrada y busque sum – val1 -val2 en el diccionario.

La ventaja de esto es que la matriz original no se modifica, pero esta versión usa memoria O (n) suplementaria. También es un poco difícil de implementar si se le permite usar solo valores distintos porque es posible que desee almacenar el índice o realizar los pasos 1 y 2 al mismo tiempo, asegurándose de que ninguno de los valores del par de elementos seleccionado esté en El diccionario todavía. Puedo entrar en más detalles si quieres.

Si tuviera que implementar esto, definitivamente elegiría la solución que mencionó porque, como ya dije, es simple de implementar y es óptima. Intenta resolver el problema en LeetCode también.

Editar:
El problema es de complejidad Omega (n ^ 2), lo que significa que no se puede encontrar una solución que sea mejor que O (n ^ 2)

Creo que el algoritmo mencionado por usted es óptimo tanto en términos de tiempo como de espacio. Aquí está mi implementación de Java que hace uso del método de dos sumas para encontrar tres sumas.

clase pública ThreeSum {
// se supone que la matriz está ordenada en orden no decreciente
public static int [] twoSumSortedArray (int [] array, int sum, int indexNotToBeConsidered) {
if (nulo == matriz) {
volver nulo;
} más {
int [] resultado = nuevo int [2];
int inicio = 0;
int end = array.length – 1;
int tempSum = 0;
if (inicio == indexNotToBeConsidered) {
inicio ++;
}
if (end == indexNotToBeConsidered) {
fin-;
}
while (inicio tempSum = array [inicio] + array [fin];
if (tempSum == sum) {
resultado [0] = inicio;
resultado [1] = fin;
resultado de retorno;
} else if (tempSum inicio ++;
} más {
fin-;
}
if (inicio == indexNotToBeConsidered) {
inicio ++;
}
if (end == indexNotToBeConsidered) {
fin-;
}
}
volver nulo;
}
}

public static int [] threeSumSortedArray (int [] array, int sum) {
if (nulo == matriz) {
volver nulo;
} más {
int [] resultado = nuevo int [3];
int [] tempResult = nulo;
for (int i = 0; i tempResult = twoSumSortedArray (matriz, suma – matriz [i], i);
if (tempResult! = null) {
resultado [0] = i;
resultado [1] = tempResult [0];
resultado [2] = tempResult [1];
resultado de retorno;
}
}
}
volver nulo;
}

public static void showArray (int [] array) {
if (nulo == matriz) {
regreso;
} más {
for (int i = 0; i System.out.print (array [i] + “”);
}
System.out.println ();
}
}

public static void showResult (int [] array, int [] indexes, int sum) {
if (null == array || indexes == null) {
System.out.println (“No se encontraron resultados para la suma:” + suma);
} más {
System.out.println (matriz [índices [0]] + “+” + matriz [índices [1]] + “+” + matriz [índices [2]] + “=” + suma);
}
}

prueba de vacío estático público con números aleatorios () {
int [] array = nuevo int [20];

for (int i = 0; i matriz [i] = (int) (Math.random () * 20);
}
Arrays.sort (matriz);
showArray (matriz);

para (int i = 0; i <10; i ++) {
int sum = (int) (Math.random () * 200);
int [] índices = threeSumSortedArray (matriz, suma);
showResult (matriz, índices, suma);
}
}

prueba de vacío estático públicoWithGivenData () {
int [] array = {2, 5, 7, 1, 7, 9, 3, 9, 23, 21, 9, 0, -1, -5};
Arrays.sort (matriz);
showArray (matriz);
int [] índices = threeSumSortedArray (matriz, 19); // -5 + 1 + 23
showResult (matriz, índices, 19);

índices = threeSumSortedArray (matriz, 4); // -5 + 0 + 9
showResult (matriz, índices, 4);

índices = threeSumSortedArray (matriz, 1000); // Extraviado
showResult (matriz, índices, 1000);

}

public static void main (String [] args) {
testingWithRandomNumbers ();
testingWithGivenData ();
}
}

Para todos los propósitos y propósitos prácticos, el algoritmo en [math] \ Theta (n ^ 2) [/ math] es el mejor.

Una respuesta más precisa a su pregunta sería: “Depende”.

En cuanto al tiempo de CPU real, probablemente no obtendrá uno mejor con un algoritmo [matemático] \ Theta (n ^ 2) [/ matemático]: los factores constantes para el que conoce son bastante bajos, y también es amigable para el caché Si desea superarlo, lo más probable es que necesite encontrar uno con una complejidad de tiempo asintóticamente mejor.

Es un poco difícil definir “el algoritmo más rápido” porque demasiados detalles pequeños importan en este caso. Ejemplos de esos pequeños detalles:

• ¿Qué tan grandes son los enteros con los que está trabajando?
• ¿Qué operaciones puedes hacer en esos enteros en tiempo constante?

Para algunas combinaciones de respuestas a esas preguntas, el tiempo cuadrático es probablemente el mejor que puede obtener. Por ejemplo, los resultados en el documento “Erickson: límites inferiores para problemas de satisfacción lineal” implican lo siguiente: no puede resolver 3SUM en [matemáticas] o (n ^ 2) [/ matemáticas] si todas las decisiones que toma su programa se basan en en el signo de una combinación lineal de tres o menos de los números de entrada. (Por ejemplo, puede comparar A [x] -A [y] y 3A [z], si lo desea. O, lo que probablemente sea más útil en nuestro caso, compare A [x] + A [y] + A [z] a 0, o A [x] + A [y] a -A [z].)

En algunos otros modelos, se conocen algoritmos subcuadráticos. El artículo “Baran, Demaine, Patrascu: Algoritmos subcuadráticos para 3SUM” muestra algunos de estos. En todos los casos, estos algoritmos son de un interés puramente teórico, la mejora (desde el punto de vista asintótico) es insignificante.

También es posible una solución subcuadrática si los números de entrada provienen de un rango muy pequeño (aproximadamente: sus valores absolutos deberían ser todos menores que [math] n ^ 2 / \ log n [/ math]).

Actualización: Gronlund y Pettie presentaron un algoritmo determinista subcuadrático en FOCS 2014: Tríos, Degenerados y Triángulos de Amor.

Es posible hacerlo mejor si los elementos están en un rango [matemática] [- N,…, N] [/ matemática] usando la Transformada rápida de Fourier (FFT) para lograr una complejidad de [matemática] \ matemática {O} (N \ log {} N) [/ math].

Puede probar el problema C de SWERC’2014 ya que requería tal solución. También hay un análisis de problemas allí, y soluciones de muestra.

El problema es que al buscar el “mejor algoritmo” en términos de encontrar una mejor constante o un mejor tiempo de CPU, es que has hecho la pregunta sin límites. La constante real en la expresión big-O está determinada por muchos supuestos de grano fino, y generalmente está sujeta a ajustes; proponer una implementación específica y alguien generalmente puede encontrar un ajuste para mejorar la constante en alguna fracción.

Del mismo modo, el tiempo de la CPU depende inherentemente de, ¿qué CPU?

Estas cuestiones explican por qué hablamos de algoritmos en términos de su comportamiento asintótico.

Sí, según tengo entendido, no puedes hacerlo mejor que O (n ^ 2). Aunque puedes hacerlo en O (n ^ 2) sin Hashmap. Por favor lea LeetCode – 3Sum. Espero que sea de ayuda 🙂.

No tuve tiempo de saber todo sobre The 3-Sum, pero este enlace puede decir algo útil en la página mit.edu

también verifique esto [1404.0799] Tríos, degenerados y triángulos amorosos