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

Modèle 1 : fenêtre constante (comme la 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) Plus grand sous-tableau/sous-chaîne avec exemple : sum

• Approches:
  • Force Brute : Générez tous les sous-tableaux possibles et choisissez le sous-tableau de longueur maximale avec somme
• Mieux/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 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
  • Trouver le sous-tableau où sum

Modèle 4 : Trouver la fenêtre la plus courte/minimale

Différentes approches pour le modèle 2 :
Exemple : Le plus grand sous-tableau avec somme

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) break; /// optimization if the sum is greater than the k, what is the point in going forward? 
            }
        }

Meilleure approche en utilisant les deux pointeurs et la fenêtre coulissante

        //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 k){
                sum = sum-arr[left];
                left  ;
            }
            if(sum 



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 ( maxLen, alors seul maxLen sera mis à jour.

Une approche optimale consistera à réduire uniquement la gauche tant que la longueur du sous-tableau est supérieure à maxLen lorsque le sous-tableau ne satisfait pas à la condition (


        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