Zwei-Zeiger- und Schiebefenstermuster

Zwei-Zeiger- und Schiebefenstermuster

Muster 1: Konstantes Fenster (wie Fenster = 4 oder ein ganzzahliger Wert)

Ermitteln Sie beispielsweise bei einem gegebenen Array von (-ve und +ve)-Ganzzahlen die maximale Summe für das zusammenhängende Fenster der Größe k.

Muster 2:(Variable Fenstergröße) Größtes Subarray/Teilzeichenfolge mit Beispiel: Summe <=k.

• Ansätze:
  • Brute Force: Generieren Sie alle möglichen Subarrays und wählen Sie das Subarray mit der maximalen Länge mit Summe <=k (dies wird eine zeitliche Komplexität von $O(n^2)$ haben.
• Besser/Optimal: Nutzen Sie zwei Zeiger und ein Schiebefenster, um die Zeitkomplexität auf O(n) zu reduzieren.

Muster 3: Anzahl der Subarrays/Substrings, wobei wie sum=k.
Dies ist sehr schwer zu lösen, da es schwierig wird, wann man expandiert (rechts++) oder wann man schrumpft (links++).

Dieses Problem kann mit Muster 2
gelöst werden Zum Lösen von Problemen wie dem Ermitteln der Anzahl von Teilzeichenfolgen, bei denen Summe =k.

• Dies kann wie folgt unterteilt werden:

  • Suchen Sie Subarrays, bei denen sum<=k ----X
  • Suchen Sie ein Subarray, in dem sum<=k-1----Y ist dann ist das Ergebnis X-Y = Antwort

Muster 4: Finden Sie das kürzeste/minimale Fenster

Verschiedene Ansätze für Muster 2:
Beispiel: Größtes Subarray mit Summe<=k

public class Sample{
    public static void main(String args[]){
        n = 10;
        int arr[] = new int[n];

        //Brute force approach for finding the longest subarray with sum <=k
        //tc : O(n^2)
        int maxlen=0;
        for(int i =0;i<arr.length;i++){
            int sum =0;
            for(int j = i+1;j<arr.length;j++){
                sum+=arr[j];
                if(sum<=k){
                    maxLen = Integer.max(maxLen, j-i+1);
                }
                else if(sum > k) break; /// optimization if the sum is greater than the k, what is the point in going forward? 
            }
        }




<p><strong>Bessere Annäherung mit den beiden Zeigern und dem Schiebefenster</strong><br>
</p>

<pre class="brush:php;toolbar:false">        //O(n+n) in the worst case r will move from 0 to n and in the worst case left will move from 0 0 n as well so 2n
        int left = 0;
        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right<arr.length){
            sum+=arr[right];
            while(sum > k){
                sum = sum-arr[left];
                left++;
            }
            if(sum <=k){
                maxLen = Integer.max(maxLen, right-left+1); //if asked to print max subarray length,we print maxLen else asked for printing the subarray keep track of
                // left and right in a different variable 
            }
            right++;
        }

Optimaler Ansatz:
Wir wissen, dass wir, wenn wir das Subarray finden, seine Länge in maxLen speichern, aber wenn wir beim Hinzufügen von arr[right] die Summe größer als k werden, verkleinern wir derzeit nach links, indem wir sum = sum-arr[left] und left++ ausführen.
Wir wissen, dass die aktuelle maximale Länge maxLen ist. Wenn wir den linken Index weiter verkleinern, erhalten wir möglicherweise ein weiteres Subarray, das die Bedingung erfüllt (<=k), aber die Länge ist möglicherweise kleiner als die aktuelle maxLen. Dann werden wir maxLen nicht aktualisieren Wir finden ein weiteres Subarray, das die Bedingung erfüllt und außerdem len > maxLen, dann wird nur maxLen aktualisiert.

Ein optimaler Ansatz besteht darin, die linke Seite nur zu verkleinern, solange die Subarray-Länge größer als maxLen ist, wenn das Subarray die Bedingung (<=k)int left = 0 nicht erfüllt.

        int right =0;
        int sum = 0;
        int maxLen = 0;
        while(right k){// this will ensure that the left is incremented one by one (not till the sum<=k because this might reduce the length i.e right-left+1  which will not be taken into consideration)
                sum = sum-arr[left];
                left++;
            }
            if(sum <=k){
                maxLen = Integer.max(maxLen, right-left+1); //if asked to print max subarray length,we print maxLen else asked for printing the subarray keep track of
                // left and right in a different variable 
            }
            right++;
        }

    }
}






          

            
  

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