Sliding window (janela deslizante) / Two pointers (dois ponteiros)
Ao trabalhar com arrays, a técnica de sliding window é muito utilizada para resolver problemas de forma eficiente apenas com two pointers. A ideia principal desta abordagem é ter um ponteiro à esquerda e outro à direita, movendo-os na direção adequada sempre que necessário.
Imagine que o objetivo seja encontrar um subarray perfeito numa lista. Primeiro, deslocamos o ponteiro da direita o máximo possível; em seguida, ajustamos o ponteiro da esquerda, aproximando-o do da direita. Depois, voltamos a deslocar o ponteiro da direita e, novamente, aproximamos o da esquerda. Repetimos este processo até identificar o melhor intervalo possível — e é precisamente essa técnica que chamamos de sliding window.
Desafio - Encontrar dois números que somam a k
Dado um array ordenado de
n números e um valor alvo k, é pedido que se encontrem dois números desse array cuja soma seja k. Note que os valores do array encontram-se em ordem crescente. Não é permitido recorrer a dicionários, mapas, hashmaps, etc.Entrada
A primeira linha de entrada contém dois inteiros —
n, o número de elementos do array (1 ≤ n ≤ ), e k . A linha seguinte contém n inteiros separados por um espaço, que representam os elementos do array em ordem crescente.Saída
O programa deve imprimir dois inteiros do array que somem
k. O primeiro inteiro deverá ser o menor possível. Se não for possível encontrar tais dois números, o programa deve imprimir Impossible.Exemplos
Entrada | Saída |
5 11
-2 3 4 8 9 | 3 8 |
5 1000
-2 3 4 8 9 | Impossible |
Tutorial
Como o array está em ordem crescente, podemos começar com dois ponteiros: um no início e outro no final do array, e ajustá-los com base na soma que obtemos.
Se a soma desses dois elementos for maior que
k, deslocamos o ponteiro da direita para a esquerda. Se a soma for menor, deslocamos o ponteiro da esquerda para a direita. Se a soma for exatamente k, imprimimos esses elementos e terminamos o programa.n, k = ... # Inicializar n e k
a = ... # Inicializar o array (já está em ordem crescente)
l, r = 0, len(a) - 1 # Inicializar ponteiros da esquerda e da direita
while l < r: # Enquanto l e r não se cruzarem
if a[l] + a[r] > k: # Se a soma for maior que k => reduzir r
r -= 1
elif a[l] + a[r] < k: # Se a soma for menor que k => avançar l
l += 1
else: # a[l] + a[r] == k => imprimir resultado e sair
print(a[l], a[r])
break
else: # while...else = não houve break -> não encontrámos nada
print('Impossible')“Two-pointers” é um método genérico que pode ser aplicado em diferentes cenários. A ideia central é escolher posições iniciais para os dois ponteiros (que podem variar de problema para problema) e definir a forma como vamos atualizá-los (também pode diferir conforme o contexto).
Neste caso, posicionámos o ponteiro esquerdo no início do array e o direito no fim. Porém, noutros problemas, podemos começar ambos no início ou mesmo colocar o ponteiro esquerdo no final, deslocando ambos em direção ao início do array. O essencial é adaptar o posicionamento e as regras de deslocamento às exigências de cada situação.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB