Leetcode: dos sumas y un enfoque intuitivo

Imagínese como el orgulloso propietario de una tienda de souvenirs dentro del Spot-On Change Hotel. Al cerrar la caja te das cuenta de un exceso de 8 euros. Parece que un huésped no recibió el cambio exacto. Esto podría empañar la reputación del hotel. Para evitarlo, decides resolver el misterio del cambio incorrecto. Al abrir el sistema de efectivo de la tienda, descubres que el error se produjo en dos cuentas diferentes.

Idea un plan: visitar cada habitación y preguntar a los invitados qué cambio recibieron en la tienda hasta encontrar a los dos con la factura equivocada. Al llegar al primer piso, un huésped informa haber recibido 4 euros de cambio. Calculas que necesitas encontrar un número que sumado a los 4 euros dé como resultado 8. Pasando al segundo piso, el cambio del huésped es de 5 euros. 4 + 5 da como resultado 9, así que no puede ser este… Quinto piso, sexto… Décimo, ¡NO, NO, NO!

Como no encontraste el valor en el primer intento, bajas al segundo piso y comienzas a preguntar nuevamente a todos los invitados sobre su cambio para poder compararlo con el valor del siguiente piso inicial, agotador, ¿no? ¿él? En informática, este método de búsqueda se llama fuerza bruta, un método de búsqueda extremadamente lento que funciona comparando un elemento con los siguientes en la matriz.

Esto consume mucho tiempo y no es eficiente, ¡imagínate subir y bajar todos los pisos del Spot-On Change Hotel varias veces! Esto no es práctico para usted ni tampoco para la computadora.

Si tiene curiosidad acerca de cómo sería esto de subir y bajar los pisos en un programa de software, se vería así en JavaScript:

 twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } }

Después de evaluar la situación con calma, te das cuenta de que hay una forma más eficaz de encontrar a los dos invitados con el cambio equivocado.

Afinas tu intuición matemática inicial de que 9 euros equivalen a x + y. Aplicando un poco de aritmética te das cuenta de que: x + y = 9 es lo mismo que decir que y = 9 — x, y eso marca la diferencia a la hora de aumentar la eficiencia de tu búsqueda.

Otra cosa que cambió en tu estrategia es que ahora llevarás un bloc de notas para anotar los valores que te dicen los invitados, así no tendrás que pedir dos veces el mismo valor a los invitados, y no tendrás que gastar. el día subiendo y bajando escaleras. (¡Qué momento tan terrible para que se estropee el ascensor!).

Con las nuevas herramientas en mano, te diriges al primer piso, donde un huésped te informa que tiene 5 euros de cambio. Registra esto como {5: 0}, lo que indica un valor de 5 en la posición 0. Sustituyendo x por 5 en la ecuación, calcula y = 8–5, lo que da como resultado y = 3. Como su bloc de notas todavía está vacío, no No tienes anotado el número 3, que sería el número complementario al 5 para llegar al resultado 8. Luego anotas en tu libreta el número 5 (recuerda anotar siempre el número verificado en el momento y no su complemento; solo usará el complemento para compararlo con el número objetivo que has anotado). Continúas con el segundo huésped, quien menciona recibir 2 euros de cambio. Aplicando nuevamente la fórmula: y = 8–2 => y = 6, verificas tu registro, donde no encuentras ningún número 6. Por lo tanto, sumas el 2 a tu registro, que ahora queda como {5: 0, 2: 1}. Continuando con la búsqueda, el siguiente huésped informa haber recibido 3 euros de cambio. Calculas de nuevo: y = 8–3 => y = 5. ¡Bingo! ¡Tienes un 5 anotado en tu libreta! ¡El huésped del piso 0 es complementario al del piso 2! Este enfoque se conoce como tabla hash y es mucho más rápido y eficiente, tanto para usted como para la computadora. En JavaScript, esto se implementaría de la siguiente manera:

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

Este es un problema sencillo de Leetcode que sólo se vuelve fácil después de comprender los conceptos detrás de él. Le recomiendo que intente resolver el problema usted mismo y dedique algún tiempo a intentar desarrollar la intuición detrás de él, crear su propia analogía, revisar e intentar escribir pseudocódigo antes de pasar a la solución.

Espero que mi analogía te haya ayudado a comprender mejor los conceptos detrás del desafío de las dos sumas.

¡Hasta la próxima!