Estoy tratando de escribir una función que tomará una matriz y un número entero de destino . Como resultado, quiero devolver todos los pares posibles, en los que la suma del par sea menor que el entero objetivo. El resultado debe evitar duplicados. Por ejemplo: [2,4] y [4,2] son lo mismo.
Ejemplo: Entrada:[1,2,2,3,4,5], 6 Salida:[[1,2],[1,3],[1,4],[2,2]]
A continuación se muestra lo que puedo pensar, pero el problema es que tendrá duplicados, y también es un bucle anidado que tiene n cuadrados para O grande en términos de complejidad de tiempo. ¿Hay una solución mejor? y ¿cómo puedo deshacerme de los duplicados?
function twoNumSum(array, targetNum) { let result = []; for (i = 0; i < array.length; i++) { for (j = i + 1; j < array.length; j++) { if (array[i] + array[j] < targetNum) { if (!result[(array[i], array[j])]) { result.push([array[i], array[j]]); } } } } return result; } //Test for my solution console.log(twoNumSum([1, 2, 3, 4], 4));//output=[1,2] console.log(twoNumSum([1, 2, 3], 3)),6//output=[] console.log(twoNumSum([1, 2, 2, 3, 4], 5));//output=[[1,2],[1,2],[1,3],[2,2] DUPLICATES of [1,2]Considere el escenario donde cada par posible en la matriz tiene una suma menor que el objetivo (algo así como [1,2,3,4] , target=10 ). Hay n^2 pares válidos, por lo que es poco probable que su complejidad de tiempo sea mejor que O(n^2) .
Para manejar duplicados, puede ordenar los pares como [smaller element, bigger element] y almacenar los pares en un conjunto.
puede modificar ligeramente su implementación usando Set , JSON.stringify y JSON.parse
Set de no tener duplicados, pero para hacerlo en una matriz, lo convertí en una cadena json.
Cuando tenga sus valores únicos, puede transformar el Conjunto en una matriz y analizar la cadena json nuevamente en una matriz
function twoNumSum(array, targetNum) { let result = new Set(); for (i = 0; i < array.length; i++) { for (j = i + 1; j < array.length; j++) { if (array[i] + array[j] < targetNum) { result.add(JSON.stringify([array[i], array[j]])); } } } return [...result].map(JSON.parse); } //Test for my solution console.log(twoNumSum([1, 2, 2, 3, 4], 6))Para evitar duplicados, he usado Object en lugar de Array para almacenar pares
Antes de agregar un par, verifique primero si los pares no están en claves de objeto
!(pairs.toString() in result) Usé dos bucles, el segundo comienza desde el siguiente del índice actual i ( para evitar comparar el primer par consigo mismo )
for (let j = i + 1; j < array.length - i - 1; j++) function twoNumSum(array, targetNum) { let result = {}; for (i = 0; i < array.length; i++) { const currNumber = array[i]; for (let j = i + 1; j < array.length - i - 1; j++) { const nextNumber = array[j]; const pairs = [currNumber, nextNumber]; const innserSum = pairs[0] + pairs[1]; if (innserSum < targetNum && !(pairs.toString() in result)) { result[pairs] = pairs; } } } return Object.values(result); } console.log(JSON.stringify(twoNumSum([1, 2, 2, 3, 4], 6))); //[[1,2],[1,3],[2,2]]