1. Información general
En este tutorial rápido, mostraremos cómo implementar un algoritmo para encontrar todos los pares de números en una matriz cuya suma sea igual a un número dado. Nos centraremos en dos enfoques del problema .
En el primer enfoque, encontraremos todos esos pares independientemente de su singularidad. En el segundo, encontraremos solo las combinaciones de números únicos, eliminando los pares redundantes.
Para cada enfoque, presentaremos dos implementaciones: una implementación tradicional que usa bucles for y una segunda que usa Java 8 Stream API.
2. Devolver todos los pares coincidentes
Iremos a través de una matriz de números enteros, encontrando todos los pares ( i y j ) que sumen el número dado ( suma ) utilizando un enfoque de bucle anidado de fuerza bruta. Este algoritmo tendrá una complejidad en tiempo de ejecución de O (n2) .
Para nuestras demostraciones, buscaremos todos los pares de números cuya suma sea igual a 6 , usando la siguiente matriz de entrada :
int[] input = { 2, 4, 3, 3 }; En este enfoque, nuestro algoritmo debería devolver:
{2,4}, {4,2}, {3,3}, {3,3}En cada uno de los algoritmos, cuando encontramos un par de números objetivo que suman el número objetivo, recopilaremos el par utilizando un método de utilidad, addPairs (i, j) .
La primera forma en que podríamos pensar en implementar la solución es mediante el tradicional bucle for :
for (int i = 0; i < input.length; i++) { for (int j = 0; j < input.length; j++) { if (j != i && (input[i] + input[j]) == sum) { addPairs(input[i], sum-input[i])); } } }Esto puede ser un poco rudimentario, así que también escribamos una implementación utilizando la API de Java 8 Stream .
Aquí, usamos el método IntStream.range para generar un flujo secuencial de números. Luego, los filtramos por nuestra condición: número 1 + número 2 = suma :
IntStream.range(0, input.length) .forEach(i -> IntStream.range(0, input.length) .filter(j -> i != j && input[i] + input[j] == sum) .forEach(j -> addPairs(input[i], input[j])) ); 3. Devolver todos los pares coincidentes únicos
Para este ejemplo, tendremos que desarrollar un algoritmo más inteligente que devuelva solo las combinaciones de números únicos, omitiendo los pares redundantes .
Para lograr esto, agregaremos cada elemento a un mapa hash (sin ordenar), verificando primero si el par ya se ha mostrado. Si no, lo recuperaremos y lo marcaremos como se muestra (establecer el campo de valor como nulo ).
En consecuencia, utilizando la misma matriz de entrada que antes y una suma objetivo de 6 , nuestro algoritmo debería devolver solo las diferentes combinaciones de números:
{2,4}, {3,3}Si usamos un bucle for tradicional , tendremos:
Map pairs = new HashMap(); for (int i : input) { if (pairs.containsKey(i)) { if (pairs.get(i) != null) { addPairs(i, sum-i); } pairs.put(sum - i, null); } else if (!pairs.containsValue(i)) { pairs.put(sum-i, i); } }Tenga en cuenta que esta implementación mejora la complejidad anterior, ya que usamos solo un bucle for , por lo que tendremos O (n) .
Ahora solucionemos el problema usando Java 8 y la API Stream:
Map pairs = new HashMap(); IntStream.range(0, input.length).forEach(i -> { if (pairs.containsKey(input[i])) { if (pairs.get(input[i]) != null) { addPairs(input[i], sum - input[i]); } pairs.put(sum - input[i], null); } else if (!pairs.containsValue(input[i])) { pairs.put(sum - input[i], input[i]); } });4. Conclusión
En este artículo, explicamos varias formas diferentes de encontrar todos los pares que suman un número dado en Java. Vimos dos soluciones diferentes, cada una con dos métodos principales de Java.
Como de costumbre, todos los ejemplos de código que se muestran en este artículo se pueden encontrar en GitHub; este es un proyecto de Maven, por lo que debería ser fácil de compilar y ejecutar.