Zwei Zeiger: entgegengesetzte Enden
Verwenden Sie einen linken und einen rechten Zeiger, die sich aufeinander zubewegen, um Paarsummen in sortierten Arrays, gültige Palindrome und das Auffangen von Regenwasser zu lösen.
Zwei Zeiger: entgegengesetzte Enden ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Die Zwei-Zeiger-Idee
Die Zwei-Zeiger-Technik verwendet zwei Indexvariablen, die sich aufeinander zu oder in dieselbe Richtung bewegen, um verschachtelte Schleifen möglichst zu vermeiden. Statt jedes Paar in O(n²) zu prüfen, machen Sie mit jedem Vergleich Fortschritte und kommen in O(n) zum Ergebnis. In den meisten Fällen muss das Array zuvor sortiert werden, da Sie anhand der Sortierung ableiten können, in welche Richtung sich die einzelnen Zeiger bewegen müssen, je nachdem, ob die aktuelle Paarsumme zu groß oder zu klein ist.
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []Zwei-Summen-Problem in einem sortierten Array
Setzen Sie bei einem sortierten Array einen Zeiger an das linke Ende (kleinstes Element) und einen am rechten Ende (größtes Element). Ist die Summe zu klein, bewegen Sie den linken Zeiger nach rechts, um sie zu vergrößern. Ist die Summe zu groß, bewegen Sie den rechten Zeiger nach links, um sie zu verkleinern. Jede Iteration bewegt mindestens einen Zeiger, sodass die Schleife höchstens n-mal ausgeführt wird: insgesamt O(n) nach der Sortierung. Wichtig ist, dass jede Bewegung aufgrund der sortierten Reihenfolge nachweislich korrekt ist.
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]Gültiges Palindrom prüfen
Eine Zeichenkette ist ein Palindrom, wenn sie vorwärts und rückwärts gleich gelesen wird. Verwenden Sie zwei Zeiger, die an den beiden Enden beginnen und sich zur Mitte bewegen: Vergleichen Sie die Zeichen, überspringen Sie nicht alphanumerische Zeichen und halten Sie an, wenn sich die Zeiger kreuzen. Dies benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz – deutlich übersichtlicher als das Umdrehen und Vergleichen der Zeichenkette, wobei O(n) zusätzlicher Speicher reserviert wird.
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseDrei-Summen-Problem: Sortieren + zwei Zeiger
Beim Drei-Summen-Problem sollen alle eindeutigen Tripel gefunden werden, deren Summe null ergibt. Sortieren Sie das Array, fixieren Sie anschließend jedes Element nums[i] und führen Sie im verbleibenden Teilarray eine Zwei-Zeiger-Suche nach einem Paar durch, dessen Summe -nums[i] ergibt. Überspringen Sie Duplikate sowohl des fixierten Elements als auch des gefundenen Paars, um wiederholte Tripel zu vermeiden. Gesamtzeit: O(n²) nach einer Sortierung in O(n log n).
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]Container mit dem meisten Wasser
Bei gegebenen Höhen vertikaler Linien sollen Sie zwei Linien finden, die einen Container bilden, der die größte Wassermenge aufnehmen kann. Fläche = min(height[left], height[right]) × (right - left). Bewegen Sie den Zeiger an der kürzeren Linie nach innen: Wenn Sie den Zeiger der längeren Linie bewegen, kann sich die Breite nur verringern, ohne dass die Höhenbegrenzung steigt. Diese Greedy-Entscheidung ist nachweislich optimal und benötigt O(n) Zeit.
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49Sortiertes Array quadrieren
Quadrieren Sie jedes Element eines sortierten Arrays, das negative Werte enthalten kann, und geben Sie das Ergebnis in sortierter Reihenfolge zurück. Quadrate negativer Werte sind groß, während Quadrate positiver Werte in der Mitte klein sind. Setzen Sie an beiden Enden zwei Zeiger und füllen Sie das Ergebnisarray von rechts nach links (vom größten zum kleinsten Wert). Der Zeitaufwand beträgt O(n) und der Speicherplatz für die Ausgabe O(n) – deutlich besser als Quadrieren und anschließendes Sortieren in O(n log n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Regenwasser auffangen
Das an Index i gespeicherte Wasser entspricht min(max_left, max_right) - height[i]. Zwei-Zeiger-Ansatz: Führen Sie die laufenden Werte max_left und max_right. Wenn max_left < max_right gilt, ist die linke Seite der Engpass – verarbeiten Sie den linken Zeiger. Andernfalls verarbeiten Sie den rechten. Dadurch werden separate Arrays für das linke und rechte Maximum überflüssig, sodass nur O(1) zusätzlicher Speicherplatz benötigt wird.
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6Warum die Greedy-Zeigerbewegung funktioniert
Eine häufige Nachfrage im Interview lautet: Warum ist es sicher, den kleineren Zeiger zu verwerfen? Beweisskizze für das Problem mit dem Container mit dem meisten Wasser: Angenommen, height[left] < height[right]. Jedes Paar (left, j) für j < right liefert eine Fläche ≤ height[left] × (j-left) < height[left] × (right-left) ≤ current area. Daher kann kein Paar, das bei 'left' beginnt und einen rechten Index kleiner als 'right' besitzt, die aktuelle Fläche übertreffen. Wir können diese Paare sicher überspringen, indem wir left vorrücken.
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')Paar mit minimaler Differenz in sortiertem Array
Finden Sie das Zahlenpaar in einem sortierten Array mit der kleinsten absoluten Differenz. Verwenden Sie zwei benachbarte Zeiger (nicht die entgegengesetzten Enden), die gemeinsam durch das Array laufen: |nums[i] - nums[i+1]| für alle aufeinanderfolgenden Paare. Die minimale Differenz in einem sortierten Array tritt immer zwischen benachbarten Elementen auf, weil beim Sortieren nahe beieinanderliegende Werte gruppiert werden. Dies ist nach dem Sortieren O(n).
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1Vorlage für die Zwei-Zeiger-Technik mit entgegengesetzten Enden
Die meisten Probleme mit zwei Zeigern an entgegengesetzten Enden folgen demselben Grundgerüst. Wenn Sie diese Vorlage beherrschen, können Sie sie unter Zeitdruck schnell anpassen. Die entscheidenden Fragen sind: (1) Unter welcher Bedingung wird der linke Zeiger weiterbewegt? (2) Unter welcher Bedingung wird der rechte Zeiger weiterbewegt? (3) Was gilt als Lösung? und (4) Wie werden Duplikate behandelt? Üben Sie, diese Entscheidungen aus der Aufgabenstellung abzuleiten, bevor Sie Code schreiben.
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultGültige Paare mit zwei Zeigern zählen
Zwei Zeiger können auch Paare effizient zählen. Für das Problem „Paare mit einer Summe < target zählen“ in einem sortierten Array: Fixieren Sie den linken Zeiger und verwenden Sie den rechten Zeiger, um den am weitesten rechts liegenden gültigen Index für rechts zu finden. Alle Paare (left, left+1 bis right) sind gültig — addieren Sie right - left zur Anzahl und bewegen Sie left weiter. So zählen Sie alle gültigen Paare in O(n) statt in O(n²).
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Die Zwei-Zeiger-Technik mit entgegengesetzten Enden ersetzt die Aufzählung von Paaren in O(n²) durch eine Konvergenz von links und rechts in O(n) bei sortierten Arrays, welcher Zeiger weiterbewegt wird, ergibt sich aus der Monotonieeigenschaft des Problems — bewegen Sie die Seite, die den Fortschritt derzeit begrenzt, und Three-Sum, Container With Most Water, Trapping Rain Water und die Palindromprüfung lassen sich alle auf dasselbe grundlegende Muster reduzieren. Als Nächstes untersuchen wir Muster mit langsamen und schnellen Zeigern.
Häufig gestellte Fragen
Ist die Lektion „Zwei Zeiger: entgegengesetzte Enden“ kostenlos?
Ja — der vollständige Text von „Zwei Zeiger: entgegengesetzte Enden“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Zwei Zeiger: entgegengesetzte Enden“?
Verwenden Sie einen linken und einen rechten Zeiger, die sich aufeinander zubewegen, um Paarsummen in sortierten Arrays, gültige Palindrome und das Auffangen von Regenwasser zu lösen. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Zwei Zeiger: entgegengesetzte Enden“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Array-Grundlagen und In-Place-Operationen
- Präfixsummen und laufende Summen
- Zwei Zeiger: entgegengesetzte Enden
- Zwei Zeiger: langsam und schnell