Modèle à deux pointeurs et fenêtres coulissantes

Modèles de fenêtres à deux pointeurs et coulissantes

Modèle 1 : Fenêtre constante (Comme fenêtre = 4 ou une valeur entière)

Par exemple, étant donné un tableau d'entiers (-ve et +ve), trouvez la somme maximale pour la fenêtre contiguë de taille k.

Modèle 2 : (Taille de fenêtre variable) Le plus grand sous-tableau/sous-chaîne avec exemple : somme <=k.

• Approches :
  • Force Brute : Générez tous les sous-tableaux possibles et choisissez le sous-tableau de longueur maximale avec sum <=k (cela aura une complexité temporelle de $O(n^2)$.
• Mise/Optimal : Utilisez deux pointeurs et une fenêtre coulissante pour réduire la complexité temporelle à O(n)

Modèle 3 : numéro de sous-tableau/sous-chaîne où comme sum=k.
Ceci est très difficile à résoudre car il devient difficile de savoir quand agrandir (à droite ++) ou quand rétrécir (à gauche ++).

Ce problème peut être résolu en utilisant le Modèle 2
Pour résoudre des problèmes comme trouver le nombre de sous-chaînes où sum =k.

• Cela peut être décomposé en

  • Trouver des sous-tableaux où sum<=k ----X
  • Trouver le sous-tableau où sum<=k-1----Y alors le résultat sera X-Y = réponse

Modèle 4 : Trouvez la fenêtre

Différentes approches pour le motif 2 :
Exemple : Le plus grand sous-tableau avec sum<=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>Meilleure approche en utilisant les deux pointeurs et la fenêtre coulissante</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++;
        }

Approche optimale :
Nous savons que si nous trouvons le sous-tableau, nous stockons sa longueur dans maxLen, mais en ajoutant arr[right] si la somme devient supérieure au k alors actuellement nous rétrécissons vers la gauche en faisant sum = sum-arr[left] et en faisant left++.
Nous savons que la longueur maximale actuelle est maxLen, si nous continuons à réduire l'index de gauche, nous pourrions obtenir un autre sous-tableau satisfaisant la condition (<=k) mais la longueur peut être inférieure à la maxLen actuelle, alors nous ne mettrons pas à jour le maxLen jusqu'à ce que nous trouvons un autre sous-tableau satisfaisant la condition et ayant également len ​​> maxLen, alors seul maxLen sera mis à jour.

Une approche optimale consistera à réduire la gauche uniquement tant que la longueur du sous-tableau est supérieure à maxLen lorsque le sous-tableau ne satisfait pas à la condition (<=k)int left = 0.

        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++;
        }

    }
}






          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!