Ejercicio: Tripletas.

Imagine tiene una lista no ordenada de n números enteros no repetidos los cuales pueden ser positivos, negativos o cero.  Encuentre los conjuntos de tres números cuya suma sea igual a cero. Ejemplo:

El enfoque para solucionar este problema fue el siguiente:

  1. Ordenar la lista en cuestión.
  2. Particionar la lista ordenada en dos sub-listas. Una que albergue números negativos y la otra que guarde los números restantes(es decir, los números mayores o iguales a cero).
  3. Iterar a través de los elementos de ambas sub-listas por medio de dos bucles anidados para encontrar los números cuya suma sea igual a cero.

Debido a que el paso 1 es muy claro, sólo se explicarán las implementaciones de los pasos 2 y 3. Por su parte, el paso 2 puesto en funcionamiento por medio del método getPartitionInt, el cual toma como parámetro de entrada una lista ordenada (obtenida en el paso 1) y devuelve el índice de la lista que posea el menor valor mayor o igual que cero. Más aún, éste método revisa que existan tanto números positivos como negativos en la lista, debido a que se necesitan tanto números negativos como positivos para realizar una suma igual a cero. De no cumplirse ésta condición, la función retornara -1. Por último, cabe decir que este método está basado en el algoritmo de Búsqueda Binaria por lo que su complejidad computacional es de O(log(n)).

Realizadas las revisiones correspondientes a los valores contenidos en la lista, el método triplets separa a los números negativos de los números restantes basado en la premisa de que se necesitan las siguientes combinaciones de números en la tripleta para calcular una suma igual a 0:

  • Un número negativo y dos positivos.
  • Un número positivo y dos negativos.
  • Un número negativo, un número positivo y el cero.

Por su parte, Las líneas 13 a 18 del método triplets también están basadas en ese supuesto. No obstante las líneas 15 y 17 están justificadas por medio de una ecuación. Suponiendo que x + y + z = 0, entonces x = -(y+z). De este modo, si x resultara ser negativa entonces sólo bastaría con realizar una búsqueda binaria de x en la sub-lista ordenada de números negativos. De manera contraria, si x fuera positiva, solo bastaría con hacer una búsqueda binaría de x en la sub-lista ordenada de números positivos. El método binarySearch provee tal búsqueda y por ende también posee una complejidad computacional de O(log(n)).

El código completo puede ser descargado desde aquí.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s