Two Sum
Recibes una lista de números enteros y un valor objetivo. Exactamente dos números de la lista suman el valor objetivo, y tu tarea es indicar en qué posiciones se encuentran.
Toma nums = [3, 8, 12, 5] y target = 17. El valor 12 está en el índice 2 y 5 está en el índice 3, y 12 + 5 = 17, así que la respuesta es [2, 3].
Los dos números deben provenir de dos posiciones diferentes. En [4, 2, 6] con target = 8, no está permitido usar el 4 dos veces; la respuesta es [1, 2] porque 2 + 6 = 8. Sin embargo, el mismo valor puede aparecer dos veces: en [7, 3, 7] con target = 14, la respuesta es [0, 2].
Escribe una función llamada twoSum que reciba un arreglo de enteros nums y un entero target, y devuelva un arreglo de dos índices [i, j] tales que nums[i] + nums[j] sea igual a target.
Los índices deben corresponder a dos posiciones diferentes y devolverse en orden creciente (i menor que j). Cada entrada tiene exactamente un par de este tipo.
Restricciones: 2 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9, -10^9 ≤ target ≤ 10^9.
Función
- arg1integer-array
- arg2integer
- Devuelveinteger-array
Ejemplos
- Entrada
- arg1 = [3, 8, 12, 5]arg2 = 17
- Salida
- [2, 3]
- Entrada
- arg1 = [6, 1, 4, 10]arg2 = 7
- Salida
- [0, 1]
- Entrada
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- Salida
- [1, 2]
+13 pruebas ocultas al enviar
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Probar cada par con dos bucles anidados es correcto, pero con 10,000 números eso supone unos 50 millones de comprobaciones. ¿Puedes encontrar el complemento de cada número sin volver a recorrer la lista?
Cuando te encuentras ante un valor
x, ya sabes qué valor completaría el par: el objetivo menosx. La única pregunta es si ya has pasado por ese valor antes y en qué índice.Recorre la lista una vez y mantén un mapa hash de cada valor por el que hayas pasado y su índice. En cada posición, busca primero el complemento que falta; si está en el mapa, ya tienes ambos índices. De lo contrario, almacena el valor actual y continúa. Buscar antes de almacenar es lo que impide que un número se empareje consigo mismo.
Pronto habrá una explicación completa de este problema.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def twoSum(nums, target):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
arg1 = [3, 8, 12, 5] arg2 = 17
Esperado
[2, 3]