Sliding window / Two pointers
Lorsqu’on travaille avec des tableaux, la technique de sliding window (fenêtre glissante) est très populaire pour résoudre efficacement des problèmes à l’aide de deux pointeurs. Le principe fondamental de cette approche consiste à disposer d’un pointeur gauche et d’un pointeur droit, puis à les déplacer dans la bonne direction lorsque cela s’avère nécessaire.
Imaginons que nous cherchions une plage (sous-tableau) parfaite dans un tableau. Nous faisons avancer le pointeur droit autant que possible, puis nous ajustons le pointeur gauche en le rapprochant du pointeur droit. Ensuite, nous déplaçons à nouveau le pointeur droit autant que possible avant de rapprocher encore le pointeur gauche, et ainsi de suite. Nous répétons ce procédé jusqu’à trouver la meilleure plage possible. C’est ce que l’on appelle la technique de sliding window.
Challenge - Find two numbers that sum up to k
Étant donné un tableau trié de
n nombres et une valeur cible k, vous devez trouver deux nombres de ce tableau qui donnent une somme égale à k. Notez que les valeurs du tableau sont triées dans l’ordre croissant. Vous n’êtes pas autorisé à utiliser de dictionnaires, maps, hashmaps, etc.Entrée
La première ligne de l’entrée contient deux nombres entiers -
n le nombre d’éléments dans le tableau (1 ≤ n ≤ ) et le nombre k . La ligne suivante contient n nombres entiers séparés par un espace, représentant les éléments du tableau en ordre croissant.Sortie
Le programme doit afficher deux entiers du tableau qui, additionnés, donnent
k. Le premier entier doit être aussi petit que possible. S’il est impossible de trouver une telle paire, le programme doit afficher Impossible.Exemples
Input | Output |
5 11
-2 3 4 8 9 | 3 8 |
5 1000
-2 3 4 8 9 | Impossible |
Tutoriel
Comme le tableau est trié dans l’ordre croissant, on peut commencer avec deux pointeurs : l’un au début du tableau et l’autre à la toute fin, puis les ajuster en fonction de leur somme.
Si la somme de ces deux pointeurs est supérieure à
k, on peut réduire le pointeur droit. Si la somme est inférieure à k, on peut avancer le pointeur gauche. Enfin, si la somme est exactement k, on affiche ces éléments et on termine le programme.n, k = ... # Initialiser n et k
a = ... # Initialiser le tableau (il est en ordre croissant)
l, r = 0, len(a) - 1 # Initialiser les pointeurs gauche et droit
while l < r: # Tant que l et r sont différents
if a[l] + a[r] > k: # Si la somme est supérieure => la réduire en déplaçant r
r -= 1
elif a[l] + a[r] < k: # Si la somme est inférieure => l’augmenter en déplaçant l
l += 1
else: # a[l] + a[r] == k => afficher les éléments et arrêter
print(a[l], a[r])
break
else: # while...else = aucune interruption => rien trouvé
print('Impossible')La méthode dite “two-pointers” (deux pointeurs) est une technique générique applicable à divers types de problèmes. L’idée principale est de fixer les positions de départ des deux pointeurs (qui peuvent varier selon la problématique), ainsi que la règle pour mettre à jour ces positions (celle-ci peut également changer suivant le problème).
Dans cet exemple, nous avons placé le pointeur gauche au début du tableau et le pointeur droit à la fin. Dans d’autres cas, il peut être nécessaire de positionner le pointeur droit également au début du tableau. Parfois, on peut placer le pointeur gauche à la fin et déplacer ces deux pointeurs vers le début du tableau.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB