Two Sum

Last updated Jul 31, 2023 Edit Source

• Programming
• Interviewprep
• Leetcode

Two Sum es el problema mas popular de la plataforma de Leetcode, es bastante sencillo y te ayuda a entender los basicos de las soluciones que emplean hasmaps. El enunciado dicta asi:

Dado un array de numeros enteros (nums) y un numero target retorna el indice de dos valores dentro del array que sumados den dicho target. Toma en consideracion que esta garantizado que el problema solo tiene una solucion y que no se puede reutilizar el mismo elemento dos veces

Para resolver este problema basta con entender como funciona la estructura de datos hashmap. A grandes rasgos el algoritmo dice algo asi:

1. Inicializa un Hashmap vacio donde se iran agregando los elementos
2. Itera sobre los elementos del array nums
3. Para cada elemento, calcula el numero que se necesita para que sumados, den igual al target (su complemento) target - numeroActual.
4. Comprueba si el complemento existe en el hashmap (llave).
5. Si no existe agrega el numero actual como llave con su indice actual como valor.
6. Si existe retorna su valor (el cual sera el indice en donde se encuentra el complemento) y el indice del numero actual.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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 [i, map.get(complement) as number];
		}

		map.set(nums[i], i);
	}
	
	return [];
}