Two Sum II
Algoritmo de búsqueda optimizado para arrays ordenados
Datos de entrada
El array debe estar ordenado en forma ascendente
Ejemplos:
Visualización
↑
Left
↑
Right
Pasos de ejecución
- La visualización mostrará los pasos del algoritmo aquí.
Estrategia
Two Pointers
Tiempo
O(n)
Espacio
O(1)
Diferencia del original
Índices en base 1
Cómo funciona
El algoritmo Two Sum II aprovecha que el array está ordenado para usar una técnica llamada "Two Pointers" (Dos Punteros):
- Iniciamos con un puntero izquierdo al principio del array y un puntero derecho al final.
- Calculamos la suma de los elementos en esas posiciones.
- Si la suma es igual al target, hemos encontrado la solución.
- Si la suma es menor que el target, movemos el puntero izquierdo hacia la derecha.
- Si la suma es mayor que el target, movemos el puntero derecho hacia la izquierda.
- Repetimos hasta encontrar la solución.
Ventaja clave: Esta solución tiene una complejidad espacial de O(1), ya que solo necesitamos dos punteros independientemente del tamaño del array.