Ventana deslizante / Dos punteros
Cuando trabajamos con arreglos, la técnica de ventana deslizante (sliding window) es muy popular para resolver problemas de manera eficiente utilizando solo dos punteros. La idea principal consiste en tener un puntero izquierdo y otro derecho, e irlos moviendo en la dirección correcta según sea necesario.
Imagínate que queremos encontrar un rango (subarreglo) perfecto dentro de un arreglo. Empezamos deslizando el puntero derecho tanto como sea posible, luego ajustamos el puntero izquierdo acercándolo al derecho. Después volvemos a mover el puntero derecho lo más que podamos y nuevamente reacomodamos el izquierdo. Repetimos este proceso hasta encontrar el mejor rango posible. A esta técnica se le llama ventana deslizante.
Desafío - Encontrar dos números cuya suma sea igual a k
Dado un arreglo ordenado de
n números y un valor objetivo k, se pide encontrar dos números de ese arreglo cuya suma sea k. Ten en cuenta que los valores del arreglo están ordenados en orden creciente. No se permite usar diccionarios, mapas, hashmaps, etc.Entrada
La primera línea de la entrada contiene dos enteros:
n, la cantidad de elementos del arreglo (1 ≤ n ≤ ), y k . La siguiente línea contiene n enteros separados por espacios, que representan los elementos del arreglo en orden creciente.Salida
El programa debe imprimir dos enteros del arreglo que sumen
k. El primer entero debe ser el más pequeño posible. Si no es posible encontrar tales números, el programa debe imprimir Impossible.Ejemplos
Entrada | Salida |
5 11
-2 3 4 8 9 | 3 8 |
5 1000
-2 3 4 8 9 | Impossible |
Tutorial
Dado que el arreglo está ordenado en orden creciente, podemos iniciar con dos punteros apuntando al principio y al final del arreglo, y ajustarlos según la suma que obtengan.
Si la suma de esos dos es mayor que
k, reducimos el puntero derecho. Si la suma es menor que k, aumentamos el puntero izquierdo. Finalmente, si la suma es exactamente k, imprimimos esos elementos y detenemos el programa.n, k = ... # Inicializar n y k
a = ... # Inicializar el arreglo (ordenado de forma creciente)
l, r = 0, len(a) - 1 # Inicializar los punteros izquierdo y derecho
while l < r: # Mientras l y r no sean iguales
if a[l] + a[r] > k: # Si la suma es mayor => se reduce moviendo r
r -= 1
elif a[l] + a[r] < k: # Si la suma es menor => se incrementa moviendo l
l += 1
else: # a[l] + a[r] == k => se imprimen y se detiene el programa
print(a[l], a[r])
break
else: # while...else = no se hizo break -> no encontramos nada
print('Impossible')“Dos punteros” es un método genérico que puede aplicarse en distintos escenarios. La idea principal es decidir las posiciones iniciales de los punteros izquierdo y derecho (que pueden variar mucho según el problema) y definir la regla para mover esos punteros (que también puede ser diferente de un problema a otro).
En este caso, elegimos que el puntero izquierdo inicie en el comienzo del arreglo y el derecho en el final. Sin embargo, en otros problemas podríamos colocar ambos punteros al principio, o incluso situar el puntero izquierdo al final y deslizar ambos hacia el inicio.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB