Sliding Window (Gleitendes Fenster) / Two Pointers (Zwei Zeiger)
Wenn man mit Arrays arbeitet, ist das Sliding-Window-Verfahren sehr beliebt, um Probleme effizient mit nur zwei Zeigern zu lösen. Die Hauptidee besteht darin, einen linken und einen rechten Zeiger zu verwenden und diese bei Bedarf in die passende Richtung zu bewegen.
Stellen Sie sich vor, wir wollen in einem Array einen „perfekten“ Abschnitt (Subarray) finden. Dazu schieben wir zunächst den rechten Zeiger so weit wie möglich nach rechts und passen anschließend den linken Zeiger an, indem wir ihn näher an den rechten heranrücken. Danach verschieben wir den rechten Zeiger erneut so weit es geht und passen wieder den linken Zeiger an. Diesen Vorgang wiederholen wir, bis wir den bestmöglichen Bereich gefunden haben. Dieses Verfahren wird als Sliding Window bezeichnet.
Herausforderung – Finde zwei Zahlen, die sich zu k addieren
Es ist ein sortiertes Array mit
n Zahlen und ein Zielwert k gegeben. Die Aufgabe besteht darin, zwei Zahlen aus dem Array zu finden, deren Summe k ergibt. Dabei liegt die Besonderheit darin, dass die Werte im Array in aufsteigender Reihenfolge sortiert sind und dass keine Dictionaries, Maps, Hashmaps usw. verwendet werden dürfen.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen –
n (die Anzahl der Elemente im Array; 1 ≤ n ≤ ) und k . In der nächsten Zeile stehen n ganzzahlige Werte, jeweils durch ein Leerzeichen getrennt, die die Elemente des Arrays in aufsteigender Reihenfolge repräsentieren .Ausgabe
Das Programm soll zwei Integer aus dem Array ausgeben, deren Summe
k ergibt. Dabei soll die erste ausgegebene Zahl so klein wie möglich sein. Kann kein passendes Zahlenpaar gefunden werden, soll Impossible ausgegeben werden.Beispiele
Eingabe | Ausgabe |
5 11
-2 3 4 8 9 | 3 8 |
5 1000
-2 3 4 8 9 | Impossible |
Tutorial
Da das Array bereits aufsteigend sortiert ist, können wir mit zwei Zeigern arbeiten, von denen einer auf das erste Element und der andere auf das letzte Element zeigt. Je nach Summe dieser beiden Elemente passen wir sie an.
Ist die Summe größer als
k, verringern wir den rechten Zeiger. Ist die Summe kleiner als k, vergrößern wir den linken Zeiger. Stimmt die Summe genau mit k überein, geben wir diese Elemente aus und beenden das Programm.n, k = ... # Variablen n und k initialisieren
a = ... # Array initialisieren (es ist aufsteigend sortiert)
l, r = 0, len(a) - 1 # Linken und rechten Zeiger initialisieren
while l < r: # Solange l und r unterschiedlich sind
if a[l] + a[r] > k: # Ist die Summe größer => verkleinern durch Verschieben von r
r -= 1
elif a[l] + a[r] < k: # Ist die Summe kleiner => vergrößern durch Verschieben von l
l += 1
else: # a[l] + a[r] == k => Programm beenden
print(a[l], a[r])
break
else: # while...else = kein break -> wir haben nichts gefunden
print('Impossible')„Two-Pointers“ ist ein allgemeiner Ansatz, der in verschiedenen Szenarien verwendet werden kann. Die Grundidee besteht darin, Anfangspositionen für beide Zeiger festzulegen (was von Problem zu Problem unterschiedlich sein kann) und dann Regeln zu definieren, wie diese Zeiger weiterverschoben werden.
In diesem Beispiel liegen der linke Zeiger ganz am Anfang und der rechte ganz am Ende des Arrays. In einer anderen Aufgabenstellung könnte der rechte Zeiger hingegen ebenfalls am Anfang stehen. In wieder anderen Szenarien kann es sinnvoll sein, den linken Zeiger ans Ende zu setzen und beide Zeiger dann Richtung Anfang zu verschieben.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB