Les problèmes de fenêtre coulissante sont des problèmes dans lesquels une fenêtre de taille fixe ou variable est déplacée dans une structure de données, généralement un tableau ou une chaîne, pour résoudre efficacement des problèmes basés sur des sous-ensembles continus d'éléments. Cette technique est utilisée lorsque nous devons rechercher des sous-tableaux ou des sous-chaînes selon un ensemble de conditions donné.

Technique de la fenêtre coulissante

Table des matières

• Qu’est-ce que la technique de la fenêtre coulissante ?
• Comment utiliser la technique de la fenêtre coulissante ?
• Comment identifier les problèmes de fenêtre coulissante
• Cas d'utilisation de la technique de la fenêtre coulissante
• Problèmes pratiques sur la technique de la fenêtre coulissante

Qu’est-ce que la technique de la fenêtre coulissante ?

Technique de la fenêtre coulissante est une méthode utilisée pour résoudre efficacement des problèmes qui impliquent de définir un fenêtre ou gamme dans les données d'entrée (tableaux ou chaînes), puis en déplaçant cette fenêtre sur les données pour effectuer une opération dans la fenêtre. Cette technique est couramment utilisée dans des algorithmes tels que la recherche de sous-tableaux avec une somme spécifique, la recherche de la sous-chaîne la plus longue avec des caractères uniques ou la résolution de problèmes nécessitant une fenêtre de taille fixe pour traiter efficacement les éléments.

Prenons un exemple pour bien comprendre cela, disons que nous avons un tableau de tailles N et aussi un entier K. Maintenant, nous devons calculer la somme maximale d'un sous-tableau ayant exactement la taille K. Maintenant, comment devrions-nous aborder ce problème ?

Une façon de le faire en prenant chaque sous-tableau de taille K du tableau et en découvrant la somme maximale de ces sous-tableaux. Cela peut être fait en utilisant des boucles imbriquées qui donneront O(N²) Complexité temporelle.

Mais peut-on optimiser cette approche ?

La réponse est oui, au lieu de prendre chacun K sous-tableau de taille et en calculant sa somme, nous pouvons simplement prendre un sous-tableau de taille K de 0 à l'indice K-1 et calculer sa somme. Maintenant, décalons notre plage une par une avec les itérations et mettons à jour le résultat, comme dans la prochaine itération, augmentez la gauche et pointeur droit et mettez à jour la somme précédente comme indiqué dans l'image ci-dessous :

Technique de la fenêtre coulissante

Suivez maintenant cette méthode pour chaque itération jusqu'à ce que nous atteignions la fin du tableau :

Technique de la fenêtre coulissante

insérer un filigrane dans Word

Ainsi, nous pouvons voir qu'au lieu de recalculer la somme de chaque sous-tableau de taille K, nous utilisons la fenêtre précédente de taille K et en utilisant ses résultats, nous mettons à jour la somme et décalons la fenêtre vers la droite en déplaçant les pointeurs gauche et droit, cette opération est optimale car elle prendre le temps O(1) pour décaler la plage au lieu de recalculer.

Cette approche consistant à déplacer les pointeurs et à calculer les résultats en conséquence est connue sous le nom de Technique de fenêtre coulissante .

Comment utiliser la technique de la fenêtre coulissante ?

Il existe essentiellement deux types de fenêtres coulissantes :

1. Fenêtre coulissante de taille fixe :

Les étapes générales pour résoudre ces questions en suivant les étapes ci-dessous :

• Trouvez la taille de la fenêtre requise, disons K.
• Calculez le résultat pour la 1ère fenêtre, c'est-à-dire incluez les K premiers éléments de la structure de données.
• Utilisez ensuite une boucle pour faire glisser la fenêtre de 1 et continuez à calculer le résultat fenêtre par fenêtre.

2. Fenêtre coulissante de taille variable :

Les étapes générales pour résoudre ces questions en suivant les étapes ci-dessous :

• Dans ce type de problème de fenêtre glissante, nous augmentons notre pointeur droit un par un jusqu'à ce que notre condition soit vraie.
• À tout moment, si notre condition ne correspond pas, nous réduisons la taille de notre fenêtre en augmentant le pointeur gauche.
• Encore une fois, lorsque notre condition est satisfaite, nous commençons à augmenter le pointeur droit et suivons l'étape 1.
• Nous suivons ces étapes jusqu’à atteindre la fin du tableau.

Comment identifier les problèmes de fenêtre coulissante :

• Ces problèmes nécessitent généralement de trouver le maximum/minimum Sous-tableau , Sous-chaînes qui satisfont à une condition spécifique.
• La taille du sous-tableau ou de la sous-chaîne ' K' sera donné dans certains des problèmes.
• Ces problèmes peuvent facilement être résolus en O(N²) complexité temporelle en utilisant des boucles imbriquées, en utilisant une fenêtre glissante, nous pouvons les résoudre en Sur) Complexité temporelle.
• Complexité temporelle requise : O(N) ou O(Nlog(N))
• Contraintes: N <= 10⁶, Si N est la taille du tableau/chaîne.

Cas d'utilisation de la technique de la fenêtre coulissante :

1. Pour trouver la somme maximale de tous les sous-tableaux de taille K :

Étant donné un tableau d'entiers de taille 'n', Notre objectif est de calculer la somme maximale de 'k' éléments consécutifs dans le tableau.

Saisir : arr[] = {100, 200, 300, 400}, k = 2
Sortir : 700

Saisir : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Sortir : 39
Nous obtenons la somme maximale en ajoutant un sous-tableau {4, 2, 10, 23} de taille 4.

Saisir : arr[] = {2, 3}, k = 3
Sortir : Invalide
Il n'y a pas de sous-tableau de taille 3 car la taille du tableau entier est de 2.

Approche naïve : Alors analysons le problème avec Approche par force brute . Nous commençons par le premier indice et additionnons jusqu'au kième élément. Nous le faisons pour tous les blocs ou groupes consécutifs possibles de k éléments. Cette méthode nécessite une boucle for imbriquée, la boucle for externe commence par l'élément de départ du bloc de k éléments, et la boucle interne ou imbriquée s'additionnera jusqu'au kème élément.

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

// O(n*k) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // Initialize result  int max_sum = INT_MIN;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// O(n*k) solution for finding maximum sum of // a subarray of size k #include  #include  #include  // Find maximum between two numbers. int max(int num1, int num2) {  return (num1>num2) ? num1 : num2; } // Renvoie la somme maximale dans un sous-tableau de taille k. int maxSum(int arr[], int n, int k) { // Initialiser le résultat int max_sum = INT_MIN;  // Considérez tous les blocs commençant par i.  pour (int je = 0; je< n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%d', maxSum(arr, n, k));  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// Java code O(n*k) solution for finding maximum sum of // a subarray of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // Initialize result  int max_sum = Integer.MIN_VALUE;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed by Aditya Kumar (adityakumar129)>

# code import sys # O(n * k) solution for finding # maximum sum of a subarray of size k INT_MIN = -sys.maxsize - 1 # Returns maximum sum in a # subarray of size k. def maxSum(arr, n, k): # Initialize result max_sum = INT_MIN # Consider all blocks # starting with i. for i in range(n - k + 1): current_sum = 0 for j in range(k): current_sum = current_sum + arr[i + j] # Update result if required. max_sum = max(current_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 n = len(arr) print(maxSum(arr, n, k)) # This code is contributed by mits>

// C# code here O(n*k) solution for // finding maximum sum of a subarray // of size k using System; class GFG {  // Returns maximum sum in a  // subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // Initialize result  int max_sum = int.MinValue;  // Consider all blocks starting  // with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.Max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

function maxSum(arr, n, k) {  let max_sum = 0;    // Loop from i to k  for (let i = 0; i < k; i++) {  max_sum += arr[i];  }    let window_sum = max_sum;  for (let i = k; i < n; i++) {  window_sum = window_sum - arr[i - k] + arr[i];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum; } // Driver code let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]; let k = 4; let n = arr.length; console.log(maxSum(arr, n, k));>

 // code ?>// Solution O(n*k) pour trouver la somme maximale de // un sous-tableau de taille k // Renvoie la somme maximale dans un sous-tableau de taille k. function maxSum($arr, $n, $k) { // Initialise le résultat $max_sum = PHP_INT_MIN ; // Considérez tous les blocs // commençant par i. pour ( $i = 0; $i< $n - $k + 1; $i++) { $current_sum = 0; for ( $j = 0; $j < $k; $j++) $current_sum = $current_sum + $arr[$i + $j]; // Update result if required. $max_sum = max($current_sum, $max_sum ); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67. ?>>

24>

Complexité temporelle : O(k*n) car il contient deux boucles imbriquées.
Espace auxiliaire : O(1)

Application de la technique de la fenêtre coulissante :

• Nous calculons la somme des k premiers éléments sur n termes à l'aide d'une boucle linéaire et stockons la somme dans une variable somme_fenêtre .
• Ensuite, nous traverserons linéairement le tableau jusqu'à ce qu'il atteigne la fin et garderons simultanément une trace de la somme maximale.
• Pour obtenir la somme actuelle d'un bloc de k éléments, soustrayez simplement le premier élément du bloc précédent et ajoutez le dernier élément du bloc actuel.

La représentation ci-dessous indiquera clairement comment la fenêtre glisse sur le tableau.

Considérons un tableau arr[] = {5, 2, -1, 0, 3} et valeur de k = 3 et n = 5

Il s'agit de la phase initiale où nous avons calculé la somme initiale de la fenêtre à partir de l'index 0 . À ce stade, la somme de la fenêtre est de 6. Maintenant, nous définissons la somme maximale comme current_window, c'est-à-dire 6.

Maintenant, nous faisons glisser notre fenêtre d'un indice unitaire. Par conséquent, il supprime désormais 5 de la fenêtre et ajoute 0 à la fenêtre. Par conséquent, nous obtiendrons notre nouvelle somme de fenêtre en soustrayant 5 puis en y ajoutant 0. Ainsi, notre somme de fenêtre devient maintenant 1. Nous allons maintenant comparer cette somme de fenêtre avec la somme_maximale. Comme il est plus petit, nous ne modifierons pas le maximum_sum.

De même, maintenant encore une fois, nous faisons glisser notre fenêtre d'un indice unitaire et obtenons que la nouvelle somme de la fenêtre soit 2. Encore une fois, nous vérifions si cette somme de fenêtre actuelle est supérieure à la somme maximale jusqu'à présent. Encore une fois, il est plus petit donc nous ne modifions pas le maximum_sum.
Par conséquent, pour le tableau ci-dessus, notre maximum_sum est de 6.

Vous trouverez ci-dessous le code de l'approche ci-dessus :

// O(n) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // n must be greater  if (n <= k) {  cout << 'Invalid';  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = max(max_sum, window_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; }>

// Java code for // O(n) solution for finding // maximum sum of a subarray // of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // n must be greater  if (n <= k) {  System.out.println('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed // by prerna saini.>

# O(n) solution for finding # maximum sum of a subarray of size k def maxSum(arr, k): # length of the array n = len(arr) # n must be greater than k if n <= k: print('Invalid') return -1 # Compute sum of first window of size k window_sum = sum(arr[:k]) # first sum available max_sum = window_sum # Compute the sums of remaining windows by # removing first element of previous # window and adding last element of # the current window. for i in range(n - k): window_sum = window_sum - arr[i] + arr[i + k] max_sum = max(window_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 print(maxSum(arr, k)) # This code is contributed by Kyle McClay>

// C# code for O(n) solution for finding // maximum sum of a subarray of size k using System; class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // n must be greater  if (n <= k) {  Console.WriteLine('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.Max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

>

 // O(n) solution for finding maximum sum of // a subarray of size k // Returns maximum sum in a  // subarray of size k. function maxSum( $arr, $n, $k) { // n must be greater if ($n <= $k) { echo 'Invalid'; return -1; } // Compute sum of first // window of size k $max_sum = 0; for($i = 0; $i < $k; $i++) $max_sum += $arr[$i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. $window_sum = $max_sum; for ($i = $k; $i < $n; $i++) { $window_sum += $arr[$i] - $arr[$i - $k]; $max_sum = max($max_sum, $window_sum); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67 ?>>

24>

Complexité temporelle : O(n), où n est la taille du tableau d'entrée arr[] .
Espace auxiliaire : O(1)

2. Le plus petit sous-tableau dont la somme est supérieure à une valeur donnée :

Étant donné un tableau arr[] d'entiers et d'un nombre X , la tâche consiste à trouver le plus petit sous-tableau avec une somme supérieure à la valeur donnée.

Approche:

Nous pouvons résoudre ce problème en utilisant la technique de la fenêtre coulissante et en conservant deux pointeurs : start et end pour marquer le début et la fin de la fenêtre. Nous pouvons continuer à incrémenter le pointeur de fin jusqu'à ce que la somme de la fenêtre soit inférieure ou égale à X. Lorsque la somme de la fenêtre devient supérieure à X, nous enregistrons la longueur de la fenêtre et commençons à déplacer le pointeur de début jusqu'à la somme de la fenêtre. devient inférieure ou égale à X. Maintenant, lorsque la somme devient inférieure ou égale à X, recommencez à incrémenter le pointeur de fin. Continuez à déplacer les pointeurs de début et de fin jusqu'à ce que nous ayons atteint la fin du tableau.

3. Recherchez un sous-tableau avec une somme donnée dans un tableau d'entiers non négatifs :

Étant donné un tableau arr[] d'entiers non négatifs et d'un entier somme , trouvez un sous-tableau qui s'ajoute à un donné somme .

Approche:

conversion d'une chaîne en objet json

L'idée est simple car nous savons que tous les éléments du sous-tableau sont positifs, donc si un sous-tableau a une somme supérieure à la somme donnée alors il n'y a aucune possibilité que l'ajout d'éléments au sous-tableau actuel soit égal à la somme donnée. L'idée est donc d'utiliser une approche similaire à un fenêtre coulissante .

• Commencez avec un sous-tableau vide.
• ajouter des éléments au sous-tableau jusqu'à ce que la somme soit inférieure à X (somme donnée) .
• Si la somme est supérieure à X , supprimez des éléments du commencer du sous-tableau actuel.

4. La plus petite fenêtre contenant tous les caractères de la chaîne elle-même :

Approche:

Fondamentalement, une fenêtre de caractères est maintenue à l'aide de deux pointeurs, à savoir commencer et fin . Ces commencer et fin les pointeurs peuvent être utilisés respectivement pour réduire et augmenter la taille de la fenêtre. Chaque fois que la fenêtre contient tous les caractères d'une chaîne donnée, la fenêtre est réduite du côté gauche pour supprimer les caractères supplémentaires, puis sa longueur est comparée à la plus petite fenêtre trouvée jusqu'à présent.
Si dans la fenêtre actuelle, plus aucun caractère ne peut être supprimé alors nous commençons à augmenter la taille de la fenêtre en utilisant le fin jusqu'à ce que tous les caractères distincts présents dans la chaîne soient également présents dans la fenêtre. Enfin, trouvez la taille minimale de chaque fenêtre.

Problèmes pratiques sur la technique de la fenêtre coulissante :

Articles Liés:

• R. Articles récents sur la technique des fenêtres coulissantes
• Questions pratiques sur la fenêtre coulissante
• DSA Self-Paced – Le cours le plus utilisé et le plus fiable sur DSA