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.
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:
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