Zwei-Zeiger-Trick-JavaScript-Programm

Die Doppelzeigertechnologie für JavaScript-Programme ist eine häufig verwendete algorithmische Methode zur Lösung verschiedener Probleme, die eine lineare Zeitkomplexität erfordern. Diese Technik wird häufig zur Lösung von Problemen verwendet, bei denen Arrays, Zeichenfolgen oder verknüpfte Listen gefunden, sortiert oder bearbeitet werden. Bei dieser Methode werden zwei Zeiger verwaltet, einer beginnt am Anfang der Datenstruktur und der andere beginnt am Ende. Anschließend werden sie in entgegengesetzter Richtung durchlaufen, bis eine Lösung gefunden ist.

In diesem Tutorial untersuchen wir das Konzept der Doppelzeigertechnik und wie man es mithilfe der Programmiersprache JavaScript implementiert. Beginnen wir also zuerst mit der Problemstellung und machen dann mit diesem unterhaltsamen Tutorial weiter!

Problemstellung

Überprüfen Sie bei einem in aufsteigender Reihenfolge sortierten Array A mit N ganzen Zahlen, ob es ein Elementpaar (A[i], A[j]) gibt, dessen Summe gleich X ist.

Lassen Sie uns nun anhand einiger Beispiele die Funktionsweise des oben genannten Programms verstehen.

Input: const array = [1, 3, 5, 7, 9];
   const X = 12;
Output: Pair found at indices 1 and 4

Erläuterung − In diesem Fall wird das Elementpaar (3, 9) im Eingabearray addiert, um die Zielsumme von 12 zu ergeben, und das Programm identifiziert das Elementpaar korrekt mit Index 1 und 4.

Input: const array = [1, 3, 5, 7, 9];
   const X = 9;
Output: Pair not found

Erläuterung − Wenn in diesem Fall die Zielsumme 9 beträgt, existiert kein solches Paar und die Funktion sollte „Paar nicht gefunden“ zurückgeben.

Algorithmus

Algorithmus, der den Doppelzeiger-Trick verwendet, um herauszufinden, ob es in einem sortierten Array ein Elementpaar gibt, dessen Summe einem bestimmten Zielwert entspricht -

• Zwei Zeiger initialisieren, links = 0, rechts = Array-Länge - 1.

• Wenn die linke Seite kleiner als die rechte Seite ist, führen Sie die folgenden Vorgänge aus

  • Berechnen Sie die Summe der Elemente am linken und rechten Index.

  • Wenn die Summe dem Zielwert entspricht, werden der linke Index und der rechte Index zurückgegeben.

  • Wenn die Summe kleiner als der Zielwert ist, addieren Sie links.

  • Wenn die Summe größer als der Zielwert ist, verringern Sie die rechte Seite.

• Wenn kein solches Paar existiert, geben Sie null zurück.

Der obige Algorithmus verwendet die Doppelzeigertechnik, um nach einem Paar von Elementen in einem sortierten Array zu suchen, sodass ihre Summe einem bestimmten Zielwert entspricht. Die Zeiger beginnen an beiden Enden des Arrays und bewegen sich aufeinander zu, je nachdem, wie die Summe der Elemente am Zeiger im Vergleich zum Zielwert ist. Wenn die Summe kleiner als der Zielwert ist, bewegen Sie den linken Zeiger nach rechts, um die Summe zu erhöhen. Wenn die Summe größer als der Zielwert ist, bewegen Sie den rechten Zeiger nach links, um die Summe zu verringern. Wenn die Summe dem Zielwert entspricht, gibt das Programm den Index des Elementpaars zurück. Wenn kein solches Elementpaar vorhanden ist, gibt das Programm „Paar nicht gefunden“ zurück.

Lassen Sie uns diesen Algorithmus nun anhand eines Beispiels verstehen. In diesem Beispiel verwenden wir JavaScript, um die zuvor besprochene Problemstellung zu implementieren.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

In diesem Programm haben wir die Zwei-Zeiger-Technik verwendet, um herauszufinden, ob in einem bestimmten sortierten Array ein Elementpaar vorhanden ist, dessen Summe einem bestimmten Ziel entspricht. Dazu haben wir das Array durchlaufen und die Zeiger basierend auf der Summe der Elemente verschoben Zeiger findet das Programm effizient das Elementpaar (falls vorhanden) in O(N)-Zeitkomplexität, wobei N die Anzahl der Elemente im Array ist.

function findSumPair(array, X) {
   let left = 0;
   let right = array.length - 1;
   while (left < right) {
      const sum = array[left] + array[right];
      if (sum === X) {
         console.log(`Pair found at indices ${left} and ${right}`);
         return [left, right];
      } else if (sum < X) {
         left++;
      } else {
         right--;
      }
   }
   console.log('Pair not found');
   return null;
}
const array = [1, 3, 5, 7, 9];
const X = 12;
console.log(`Array: ${array}`);
console.log(`Target sum: ${X}`);
findSumPair(array, X);

Fazit

In diesem Tutorial haben wir das Konzept der Doppelzeigertechnik untersucht und wie man es mithilfe der Programmiersprache JavaScript implementiert, um Probleme beim Suchen oder Vergleichen eines Elementpaars in einem sortierten Array zu lösen. Wir haben auch einen Algorithmus kennengelernt, um mithilfe der Zwei-Zeiger-Technik ein Elementpaar zu finden, dessen Summe einem gegebenen Ziel entspricht. Durch den Einsatz dieser Technik können wir die Effizienz unseres Programms im Hinblick auf die zeitliche Komplexität deutlich verbessern. Insbesondere kann die Doppelzeiger-Technologie diese Art von Problem mit einer Zeitkomplexität von O(N) lösen, was viel schneller ist als die Brute-Force-Methode von O(N^2). Daher ist es sehr wichtig, diese Technik zu erlernen und anzuwenden, um ähnliche Probleme effizient zu lösen.

Das obige ist der detaillierte Inhalt vonZwei-Zeiger-Trick-JavaScript-Programm. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!