[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]

Recommended Posts

Algorithmus Gymnastik 20 Paar mit Zielsumme
Algorithmusgymnastik 12
Algorithmusgymnastik 3
Algorithmusgymnastik 9
Algorithmusgymnastik 14
Algorithmusgymnastik 2
Algorithmusgymnastik 7
Algorithmus Gymnastik 15
Algorithmus Gymnastik 16
Algorithmus Gymnastik 18
Algorithmusgymnastik 11
Algorithmusübung 5
Algorithmusgymnastik 4
Algorithmus Gymnastik 24 Teilmengen
Algorithmus Gymnastik 23 Zusammenführungsintervalle
Algorithmus Gymnastik 20 Duplikate entfernen
Algorithmus Gymnastik 21 LinkedList-Zyklus
Algorithmus Gymnastik 24 Zyklische Sortierung
Algorithmus Gymnastik 19 No-Repeat-Teilzeichenfolge
[Python3] Dikstra-Methode mit 14 Zeilen
Group_by mit sqlalchemy und sum