Willkommen zurück zu unserer Blogreihe zum Thema Problemlösung in der modernen Softwareentwicklung!

In Teil 1 haben wir das Frequency Counter Pattern untersucht, eine leistungsstarke Technik zur Optimierung von Algorithmen durch effizientes Zählen der Häufigkeit von Elementen. Wenn Sie es verpasst haben oder eine kurze Auffrischung wünschen, können Sie es sich gerne ansehen, bevor Sie fortfahren.

In diesem Teil werden wir uns mit einem weiteren wesentlichen Muster befassen: dem Multipointer-Muster. Dieses Muster ist von unschätzbarem Wert, wenn es um Szenarien geht, in denen mehrere Elemente gleichzeitig verglichen, durchsucht oder durchlaufen werden müssen. Lassen Sie uns untersuchen, wie es funktioniert und wo Sie es anwenden können, um die Effizienz Ihres Codes zu verbessern.

02. Multipointer-Muster

Das Multipointer-Muster ist eine Technik, die beim Algorithmusdesign verwendet wird, bei der mehrere Zeiger (oder Iteratoren) verwendet werden, um Datenstrukturen wie Arrays oder verknüpfte Listen zu durchlaufen. Anstatt sich auf einen einzelnen Zeiger oder eine einzelne Schleife zu verlassen, verwendet dieses Muster zwei oder mehr Zeiger, die sich mit unterschiedlicher Geschwindigkeit oder von unterschiedlichen Startpunkten aus durch die Daten bewegen.

Beispielproblem

Schreiben Sie eine Funktion namens sumZero, die ein sortiertes Array von Ganzzahlen akzeptiert. Die Funktion sollte das erste Paar finden, bei dem die Summe Null ist. Wenn ein solches Paar vorhanden ist, wird ein Array zurückgegeben, das beide Werte enthält. Andernfalls geben Sie undefiniert zurück.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

Basislösung

function sumZero(arr){
    for (let i = 0; i 



Zeitkomplexität - O(N^2)

Lösung mit Multipointer-Muster

Schritt 1: Das Problem verstehen

Wir müssen zwei Zahlen in einem **sortierten-Array finden, deren Summe Null ergibt. Da das Array sortiert ist, können wir diese Reihenfolge nutzen, um die Lösung effizienter zu finden.

Schritt 2: Zwei Zeiger initialisieren

Richten Sie zwei Zeiger ein: einen (left), der am Anfang des Arrays beginnt, und den anderen (right), der am Ende beginnt.

Beispiel:



Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5




Schritt 3: Berechnen Sie die Summe der Werte an den Zeigern

Addieren Sie die Werte am linken und rechten Zeiger, um die Summe zu erhalten



Sum = -4   5 = 1




Schritt 4: Vergleichen Sie die Summe mit Null

• Wenn die Summe größer als Null ist: Bewegen Sie den rechten Zeiger einen Schritt nach links, um die Summe zu verringern.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• Wenn die Summe kleiner als Null ist: Bewegen Sie den linken Zeiger einen Schritt nach rechts, um die Summe zu erhöhen.

New Sum = -4   2 = -2
Sum is -2 



Schritt 5: Wiederholen Sie den Vorgang

Bewegen Sie die Zeiger weiter und berechnen Sie die Summe, bis sie sich treffen oder ein Paar gefunden wird.



New Sum = -3   2 = -1
Sum is -1 



Die Summe ist Null, daher gibt die Funktion [-2, 2] zurück.

Wenn die Schleife abgeschlossen wird, ohne ein solches Paar zu finden, geben Sie undefiniert zurück.

Endgültiger Code



function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left  0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left  ;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}




NOTIZ:

Zeitkomplexität: O(n) – Die Funktion ist effizient und skaliert linear mit der Größe des Arrays.

Raumkomplexität: O(1) – Die Funktion benötigt nur minimalen zusätzlichen Speicher.

Abschluss

Das Multipointer-Muster ist eine leistungsstarke Technik zur Lösung von Problemen, bei denen Elemente in einer sortierten Datenstruktur gesucht, verglichen oder bearbeitet werden. Durch die Verwendung mehrerer Zeiger, die sich aufeinander zubewegen, können wir die Effizienz von Algorithmen erheblich verbessern und in vielen Fällen die Zeitkomplexität von O(n²) auf O(n) reduzieren. Dieses Muster ist vielseitig und kann auf eine Vielzahl von Problemen angewendet werden, was es zu einer wesentlichen Strategie zur Optimierung der Leistung in Ihrem Code macht.

Bleiben Sie gespannt auf unseren nächsten Beitrag, in dem wir uns mit dem Sliding Window Pattern befassen, einem weiteren wichtigen Tool zur Lösung von Problemen mit dynamischen Datensegmenten. Es ist ein unglaublich nützliches Muster, das Ihnen helfen kann, sogar komplexere Herausforderungen mit Leichtigkeit zu lösen!