Entonces, en LeetCode, necesito devolver la suma de dos números que son iguales al número objetivo. Este es un tipo leetcode "fácil". Nunca antes había hecho leetcode, así que decidí intentarlo. Inmediatamente, pude resolver el problema, pero mi solución no era lógica porque compara cada número en la matriz entre sí. Entonces, si la entrada es un millón de dígitos, lo verificará un millón de veces para cada número.
Vale la pena señalar que aunque mi programa funciona, puede enviarse debido a que se excedió el límite de tiempo.
No estoy seguro de cuál sería la solución matemática para optimizar esto. Actualmente estoy yendo a Matemáticas nuevamente aprendiendo en qué soy débil.
Código:
var twoSum = function(nums, target) { let total = []; let inc = 1; let intVal = 0; let startingPos = nums[intVal]; let nextPos = nums[inc]; for(let x = 0; x < nums.length; x++){ // Do not check the value of position 1 with position 2 if(nums.indexOf(startingPos) === nums.lastIndexOf(nextPos)){ nextPos++; } if(startingPos + nextPos === target){ console.log(`First Value ${startingPos}`) console.log(`Second Value ${nextPos}`) console.log(`Target ${target}`) // A match has been found return [nums.indexOf(startingPos), nums.lastIndexOf(nextPos)]; } else{ // Move to next number if index 1 is not eql // nextPos++; let nextPosIndex = nums[inc]; nextPos = nums[inc]; console.log(`Values [${startingPos}], [${nextPos}]`) console.log("No Matches"); // Increment the next value to check inc++; // Reset loop if no match is found from 2nd position if(x == (nums.length - 1)){ // Increment the initial value in first pos intVal++; startingPos = nums[intVal]; // Reset values to check new numbers x = 0; inc = 1; } // check if we exhausted all options if(startingPos === undefined){ return "No Matches."; } } } }; twoSum([5, 2, 5, 5, 1, 3, 6, 8, 4, 3, 2, 7], 14)-- Antes de continuar con más problemas, me temo que estaré en este ciclo de elegir la forma más ilógica de resolver los problemas.
¿Qué puedo hacer para modificar este problema para verificar rápidamente si dos valores son iguales al objetivo?
Aquí hay un ejemplo de compilador en vivo: https://replit.com/@FPpl/SafeHeartfeltArchitect#index.js
Al iterar sobre un número, puede colocar el valor que, si coincidiera con la suma del objetivo, en una colección (con búsqueda O(1) ). Por ejemplo, si itera sobre un número 5 y el objetivo es 20, coloque 15 en la colección.
Durante una iteración, si el número que se está iterando ya existe en la colección, tiene una coincidencia con uno que encontró anteriormente y puede devolver ambos índices.
const twoSum = function(nums, target) { // For this Map, the key is the number which, if found again, is a match // eg, if target is 20, and the number 5 is iterated over // the key will be 15 // The value is the index of the prior number found - eg, index of 5 const valuesAlreadyFound = new Map(); for (let i = 0; i < nums.length; i++) { const num = nums[i]; if (valuesAlreadyFound.has(num)) { // We have a match, get both indicies: console.log('Match for values', target - num, num); return [valuesAlreadyFound.get(num), i]; } // This wasn't a match. Identify the number which, when paired, is a match const matchNeeded = target - num; valuesAlreadyFound.set(matchNeeded, i); } return 'No match'; }; console.log('Indicies found:', twoSum([5, 2, 5, 5, 1, 3, 6, 8, 4, 3, 2, 7], 14));