En un array ordenado, averigua si dos números suman target usando O(1) de espacio.
Opciones
- Un hash set de los números vistos (O(n) de espacio)
- Dos punteros desde ambos extremos, moviéndose según la suma (Opción correcta)
- Construir un árbol binario de búsqueda con todo el array
- Probar recursivamente cada pareja de números
Respuesta
Dos punteros desde ambos extremos, acercándose según la suma
Por qué
Pon un puntero al inicio (el menor) y otro al final (el mayor).
Si la suma es demasiado pequeña, mueve el puntero izquierdo a la derecha para obtener un número mayor. Si es demasiado grande, mueve el derecho a la izquierda. Si es igual, listo.
Como el array está ordenado, cada movimiento descarta con seguridad un candidato: O(n) de tiempo, sin memoria extra.
Recuerda
Array ordenado + búsqueda de parejas → dos punteros.