[PYTHON] Algorithmus Gymnastik 20 Paar mit Zielsumme

Pair with Target Sum

Geben Sie ein sortiertes Array von Zahlen und eine Summe von Objekten an, um ein Array von Arrays zu finden, dessen Summe dem angegebenen Objekt entspricht. Erstellen Sie eine Funktion, die einen Index (dh ein Paar) aus zwei Zahlen zurückgibt. Gibt den Index -1 zurück, wenn das Paar nicht vorhanden ist.

Beispiel

Input: [1, 2, 3, 4, 6], target=6 Output: [1, 3]

Input: [2, 5, 9, 11], target=11 Output: [0, 2]

Solution Ein Doppelzeiger-Ansatz ist verfügbar. Beginnen Sie mit einem Zeiger auf den Anfang des Arrays und einem Zeiger auf das Ende. Überprüfen Sie bei jedem Schritt, ob sich die Zahlen, auf die die beiden Zeiger zeigen, zum Gesamtziel addieren. Wenn ja, haben Sie ein Paar gefunden. Führen Sie andernfalls eine der folgenden zwei Aktionen aus:

1. Wenn die Summe der beiden Zahlen, auf die die beiden Zeiger zeigen, größer ist als die Summe der Ziele, bedeutet dies, dass Sie ein Paar mit einer kleineren Summe benötigen. Daher können Sie den Endzeiger dekrementieren.
2. Wenn die Summe der beiden Zahlen, auf die die beiden Zeiger zeigen, kleiner ist als die Summe der Ziele, bedeutet dies, dass ein größeres Summenpaar benötigt wird. Daher können Sie den Startzeiger erhöhen.

Implementierung

def pair_with_targetsum(arr, target_sum):
  left_pointer = 0
  right_pointer = len(arr) - 1
  while left_pointer < right_pointer:
    sum = arr[left_pointer] + arr[right_pointer]
    if sum == target_sum:
      return [left_pointer, right_pointer]
  
    if sum > target_sum:
      right_pointer -= 1
    else:
      left_pointer += 1
  return [-1, -1]