Effizientes Lösen von zwei Summen II – Das Eingabearray ist sortiert

Das Problem „Two Sum II – Input Array Is Sorted“ ist eine klassische Codierungsherausforderung, die Ihr Verständnis von Arrays und Zeigermanipulation auf die Probe stellt. Es ist auch eine großartige Gelegenheit, eine Lösung zu präsentieren, die sowohl elegant als auch effizient ist. Lassen Sie uns in das Problem eintauchen und einen optimalen Lösungsansatz erläutern.

Link zum Problem auf LeetCode

Problemstellung

Angesichts eines 1-indizierten Arrays ganzer Zahlen, das in nicht absteigender Reihenfolge sortiert ist, besteht Ihr Ziel darin, zwei Zahlen zu finden, deren Summe einem bestimmten Ziel entspricht. Sie müssen die Indizes dieser beiden Zahlen als Array [index1, index2] zurückgeben, wobei 1 <= index1 < index2 <= Zahlen.Länge. Die Lösung sollte nur konstanten zusätzlichen Platz beanspruchen.

Einschränkungen

• Die Array-Nummern werden in nicht absteigender Reihenfolge sortiert.
• Es gibt genau eine Lösung.
• Sie dürfen dasselbe Element nicht zweimal verwenden.
• Die Länge des Eingabearrays reicht von 2 bis 30.000.
• Werte im Array reichen von −1000 bis 1000.

Beispieleingaben und -ausgaben

1. Eingabe: Zahlen = [2,7,11,15], Ziel = 9
   
   Ausgabe: [1, 2]

2. Eingabe: Zahlen = [2,3,4], Ziel = 6
   
   Ausgabe: [1, 3]

3. Eingabe: Zahlen = [-1,0], Ziel = -1
   
   Ausgabe: [1, 2]

Ansatz: Zwei Hinweise

Die Einschränkungen des Problems – ein sortiertes Array und eine einzelne Lösung – machen es zu einem perfekten Kandidaten für die Zwei-Zeiger-Technik. Hier ist der Grund:

• Effizienz: Zwei Zeiger ermöglichen es uns, das Array in einem einzigen Durchgang zu durchlaufen (O(n)-Zeitkomplexität).
• Konstanter Speicherplatz: Wir vermeiden Hilfsdatenstrukturen und halten uns an die Anforderung des Problems an konstanten zusätzlichen Speicherplatz.

Durchführung

Unten finden Sie die JavaScript-Implementierung des Zwei-Zeiger-Ansatzes:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const length = nums.length;
    let rightPointer = length - 1;
    let leftPointer = 0;

    while (leftPointer < rightPointer) {
        if (nums[leftPointer] + nums[rightPointer] === target) {
            return [leftPointer + 1, rightPointer + 1];
        }
        if (nums[leftPointer] + nums[rightPointer] > target) {
            rightPointer--;
        } else {
            leftPointer++;
        }
    }
};






  
  
  Wie es funktioniert




Zwei Zeiger initialisieren:



leftPointer beginnt am Anfang des Arrays.

rightPointer beginnt am Ende des Arrays.



Iterieren Sie, bis sie sich treffen:


Berechnen Sie die Summe der Elemente bei leftPointer und rightPointer.
Wenn die Summe mit dem Ziel übereinstimmt, werden die 1-indizierten Positionen zurückgegeben.
Wenn die Summe größer als das Ziel ist, dekrementieren Sie den rechten Zeiger, um die Summe zu reduzieren.
Wenn die Summe kleiner als der Zielwert ist, erhöhen Sie den leftPointer, um die Summe zu erhöhen.



Indizes zurückgeben:

Sobald das richtige Paar gefunden wurde, endet die Schleife und gibt die Indizes zurück.





  
  
  Beispiel-Komplettlösung


Lassen Sie uns das erste Beispiel durchgehen:



Eingabe: Zahlen = [2, 7, 11, 15], Ziel = 9


Initialisierung: leftPointer = 0, rightPointer = 3




  
  
  Iterationsschritte:



Berechnen Sie Zahlen[0] Zahlen[3] = 2 15 = 17. 


Zu groß, rechten Zeiger auf 2 dekrementieren.


Berechnen Sie Zahlen[0] Zahlen[2] = 2 11 = 13. 


Immer noch zu groß, dekrementieren Sie den rechten Zeiger auf 1.


Berechnen Sie Zahlen[0] Zahlen[1] = 2 7 = 9. 


Übereinstimmung gefunden, [1, 2] zurückgeben.





  
  
  Wichtige Punkte




1-indizierte Anpassung: Das Problem gibt eine 1-basierte Indizierung an, daher addieren wir 1 zu beiden Zeigern, bevor wir zurückkehren.

Randfälle: Die Einschränkungen garantieren eine einzige Lösung, sodass wir keine leeren Arrays oder mehrere Übereinstimmungen verarbeiten müssen.

Optimierung: Durch die Verwendung des Zwei-Zeiger-Ansatzes wird sichergestellt, dass wir die O(n)-Zeitkomplexität und den konstanten Platzbedarf erfüllen.



  
  
  Abschluss


Die Zwei-Zeiger-Methode löst auf elegante Weise das Problem „Zwei Summen II – Eingabearray ist sortiert“, indem sie die sortierte Natur des Eingabearrays nutzt. Es handelt sich um eine leistungsstarke Technik, die nicht nur Effizienz gewährleistet, sondern auch Platzbeschränkungen berücksichtigt, was sie zu einem idealen Ansatz für ähnliche Probleme macht. Viel Spaß beim Codieren!


          

            
        
Das obige ist der detaillierte Inhalt vonEffizientes Lösen von zwei Summen II – Das Eingabearray ist sortiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!