LeetCode: 1. Two Sum, Solución paso a paso
Hoy quiero compartir cómo resolví el problema Two Sum de LeetCode.
Es uno de los clásicos de entrevistas técnicas y me parece un excelente punto de partida si estás practicando lógica o estructuras de datos.
Problema
Dado un arreglo de enteros nums y un entero target, se deben devolver los índices de los dos números cuya suma sea igual a target.
El problema garantiza que siempre habrá una solución, y no se puede usar el mismo número dos veces.
Ejemplo rápido
- Entrada:
nums = [2,7,11,15],target = 9
Salida esperada:[0,1]porquenums[0] + nums[1] = 2 + 7 = 9
1. Definiendo la función
Primero definiré la función que recibirá el arreglo y el número objetivo:
function twoSum(nums: number[], target: number): number[] {
// La implementación irá aquí
}
2. Creando un Map para almacenar los números vistos
Voy a usar un Map<number, number> para guardar cada número junto con su índice.
Esto me permitirá verificar si el complemento que necesito ya apareció antes.
const map = new Map<number, number>()
3. Iterando el arreglo
Recorro el arreglo con un for, procesando cada número.
for (let i = 0; i < nums.length; i++) {
// Aquí verificare cada número
}
4. Calculando el complemento
En cada iteración calculo el complemento, que es el número que necesito para alcanzar el target.
const complement = target - nums[i]
5. Verificando si ya encontré la pareja
Si el complemento ya está en el mapa, significa que tengo la combinación correcta.
En ese caso, retorno los índices correspondientes.
if (map.has(complement)) {
return [map.get(complement)!, i]
}
6. Registrando el número actual
Si no encontré el complemento, guardo el número actual con su índice para usarlo más adelante.
map.set(nums[i], i)
Código completo
function twoSum(nums: number[], target: number): number[] {
const map = new Map<number, number>()
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i]
if (map.has(complement)) {
return [map.get(complement)!, i]
}
map.set(nums[i], i)
}
return []
}
console.log(twoSum([2,7,11,15], 9)) // [0,1]
console.log(twoSum([3,2,4], 6)) // [1,2]
console.log(twoSum([3,3], 6)) // [0,1]