Sliding Window-problemen zijn problemen waarbij een venster met een vaste of variabele grootte door een datastructuur wordt verplaatst, meestal een array of string, om problemen efficiënt op te lossen op basis van doorlopende subsets van elementen. Deze techniek wordt gebruikt wanneer we subarrays of substrings moeten vinden volgens een gegeven reeks voorwaarden.

Schuifraamtechniek

Inhoudsopgave

• Wat is schuifraamtechniek?
• Hoe gebruik je de schuifraamtechniek?
• Problemen met schuiframen identificeren
• Gebruiksvoorbeelden van schuifraamtechniek
• Oefenproblemen met de schuifraamtechniek

Wat is schuifraamtechniek?

Schuifraamtechniek is een methode die wordt gebruikt om problemen efficiënt op te lossen waarbij een raam of bereik in de invoergegevens (arrays of strings) en vervolgens dat venster door de gegevens verplaatsen om een ​​bewerking binnen het venster uit te voeren. Deze techniek wordt vaak gebruikt in algoritmen zoals het vinden van subarrays met een specifieke som, het vinden van de langste substring met unieke karakters, of het oplossen van problemen waarvoor een venster met een vaste grootte nodig is om elementen efficiënt te verwerken.

Laten we een voorbeeld nemen om dit goed te begrijpen: stel dat we een reeks afmetingen hebben N en ook een geheel getal K. Nu moeten we de maximale som van een subarray met een exacte grootte berekenen K. Hoe moeten we dit probleem nu aanpakken?

Eén manier om dit te doen is door elke subarray van grootte K uit de array te nemen en de maximale som van deze subarrays te bepalen. Dit kan worden gedaan met behulp van geneste lussen die resulteren in O(N²) Tijdcomplexiteit.

Maar kunnen we deze aanpak optimaliseren?

Het antwoord is ja, in plaats van ze allemaal te nemen K subarray van grootte en de som ervan berekenen, we kunnen gewoon één subarray van K-grootte nemen van 0 tot K-1 index en de som ervan berekenen. Verschuif nu ons bereik één voor één samen met de iteraties en update het resultaat, zoals in de volgende iteratie de linkerkant vergroten en rechteraanwijzer en update de vorige som zoals weergegeven in de onderstaande afbeelding:

Schuifraamtechniek

Volg nu deze methode voor elke iteratie totdat we het einde van de array bereiken:

Schuifraamtechniek

regressietesten bij het testen van software

We kunnen dus zien dat in plaats van de som van elke subarray van K-formaat te herberekenen, we het vorige venster van grootte K gebruiken en de resultaten ervan gebruiken, we de som bijwerken en het venster naar rechts verschuiven door de aanwijzers naar links en rechts te verplaatsen. Deze bewerking is optimaal omdat deze het kost O(1) tijd om het bereik te verschuiven in plaats van opnieuw te berekenen.

Deze benadering van het verschuiven van de wijzers en het dienovereenkomstig berekenen van de resultaten staat bekend als Schuifraamtechniek .

Hoe gebruik je de schuifraamtechniek?

Er zijn grofweg twee soorten schuiframen:

1. Schuifraam met vaste afmetingen:

De algemene stappen om deze vragen op te lossen door de onderstaande stappen te volgen:

• Zoek de grootte van het gewenste venster, zeg K.
• Bereken het resultaat voor het eerste venster, d.w.z. neem de eerste K-elementen van de datastructuur op.
• Gebruik vervolgens een lus om het venster 1 te verschuiven en blijf het resultaat venster voor venster berekenen.

2. Schuifvenster met variabele grootte:

De algemene stappen om deze vragen op te lossen door de onderstaande stappen te volgen:

• Bij dit soort schuifraamproblemen verhogen we onze rechterwijzer één voor één totdat onze voorwaarde waar is.
• Als onze conditie niet overeenkomt, verkleinen we bij elke stap de grootte van ons venster door de linkeraanwijzer te vergroten.
• Nogmaals, wanneer aan onze voorwaarde is voldaan, beginnen we de rechterwijzer te verhogen en volgen we stap 1.
• We volgen deze stappen totdat we het einde van de array bereiken.

Problemen met schuiframen identificeren:

• Voor deze problemen is doorgaans het vinden van het maximum/minimum vereist Subarray , Subtekenreeksen die aan een specifieke voorwaarde voldoen.
• De grootte van de subarray of substring ‘ K’ zal bij sommige problemen gegeven worden.
• Deze problemen kunnen eenvoudig worden opgelost in O(N²) tijdcomplexiteit met behulp van geneste lussen, met behulp van een schuifvenster kunnen we deze oplossen Op) Tijdcomplexiteit.
• Vereiste tijdcomplexiteit: O(N) of O(Nlog(N))
• Beperkingen: N <= 10⁶, Als N de grootte van de array/string is.

Gebruiksvoorbeelden van schuifraamtechniek:

1. Om de maximale som van alle subarrays van grootte K te vinden:

Gegeven een array van gehele getallen van grootte 'N', Ons doel is om de maximale som te berekenen ‘k’ opeenvolgende elementen in de array.

Invoer : arr[] = {100, 200, 300, 400}, k = 2
Uitgang: 700

Invoer : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Uitgang: 39
We krijgen de maximale som door subarray {4, 2, 10, 23} van grootte 4 toe te voegen.

Invoer : arr[] = {2, 3}, k = 3
Uitgang: Ongeldig
Er is geen subarray van grootte 3, aangezien de grootte van de hele array 2 is.

Naïeve aanpak: Laten we dus het probleem analyseren met Brute force-aanpak . We beginnen met de eerste index en som tot de kth element. We doen het voor alle mogelijke opeenvolgende blokken of groepen k-elementen. Deze methode vereist een geneste for-lus, de buitenste for-lus begint met het startelement van het blok met k-elementen, en de binnenste of de geneste lus zal oplopen tot het k-de element.

Hieronder vindt u de implementatie van de bovenstaande aanpak:

// 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>getal2) ? num1: num2; } // Geeft de maximale som terug in een subarray van grootte k. int maxSum(int arr[], int n, int k) {// Initialiseer resultaat int max_sum = INT_MIN;  // Beschouw alle blokken die beginnen met i.  voor (int i = 0; ik< 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 ?>// O(n*k) oplossing voor het vinden van de maximale som van // een subarray met grootte k // Geeft de maximale som terug in een subarray met grootte k. function maxSum($arr, $n, $k) {// Initialiseer resultaat $max_sum = PHP_INT_MIN ; // Beschouw alle blokken // beginnend met i. voor ( $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>

Tijdcomplexiteit: O(k*n) omdat het twee geneste lussen bevat.
Hulpruimte: O(1)

Toepassing van de schuifraamtechniek:

• We berekenen de som van de eerste k elementen uit n termen met behulp van een lineaire lus en slaan de som op in een variabele venster_som .
• Vervolgens doorlopen we lineair de array tot deze het einde bereikt en houden tegelijkertijd de maximale som in de gaten.
• Om de huidige som van een blok met k-elementen te krijgen, trekt u gewoon het eerste element van het vorige blok af en voegt u het laatste element van het huidige blok toe.

De onderstaande weergave maakt duidelijk hoe het venster over de array schuift.

koord van lengte

Overweeg een array arr[] = {5, 2, -1, 0, 3} en waarde van k = 3 en N = 5

Dit is de beginfase waarin we de initiële venstersom hebben berekend, beginnend bij index 0. In dit stadium is de venstersom 6. Nu stellen we de maximale_som in als huidig_venster, d.w.z. 6.

Nu verschuiven we ons venster met een eenheidsindex. Daarom wordt nu 5 uit het venster verwijderd en 0 aan het venster toegevoegd. Daarom krijgen we onze nieuwe venstersom door 5 af te trekken en er vervolgens 0 bij op te tellen. Onze venstersom wordt nu dus 1. Nu vergelijken we deze venstersom met de maximale_som. Omdat deze kleiner is, zullen we de maximum_sum niet wijzigen.

Op dezelfde manier verschuiven we ons venster nu opnieuw met een eenheidsindex en verkrijgen we dat de nieuwe venstersom 2 is. Opnieuw controleren we of deze huidige venstersom groter is dan de maximale_som tot nu toe. Nogmaals, het is kleiner, dus we veranderen de maximum_sum niet.
Daarom is voor de bovenstaande array onze maximum_sum 6.

Hieronder vindt u de code voor de bovenstaande aanpak:

// 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>

Tijdcomplexiteit: Op waar N is de grootte van de invoerarray arr[] .
Hulpruimte: O(1)

2. Kleinste subarray met som groter dan een bepaalde waarde:

Gegeven een array arr[] van gehele getallen en een getal X , is het de taak om de kleinste subarray te vinden met een som groter dan de gegeven waarde.

Benadering:

We kunnen dit probleem oplossen met behulp van de Sliding Window Technique en met behoud van twee aanwijzers: begin en einde om het begin en einde van het venster te markeren. We kunnen de eindaanwijzer blijven verhogen totdat de som van het venster kleiner is dan of gelijk is aan X. Wanneer de som van het venster groter wordt dan X, registreren we de lengte van het venster en beginnen we de startaanwijzer te verplaatsen tot de som van het venster wordt kleiner dan of gelijk aan X. Als de som nu kleiner of gelijk wordt aan X, begin dan opnieuw met het verhogen van de eindaanwijzer. Blijf de begin- en eindaanwijzer verplaatsen totdat we het einde van de array hebben bereikt.

3. Zoek een subarray met een gegeven som in een array van niet-negatieve gehele getallen:

Gegeven een array arr[] van niet-negatieve gehele getallen en een geheel getal som , zoek een subarray die bijdraagt ​​aan een gegeven som .

Benadering:

Het idee is eenvoudig, omdat we weten dat alle elementen in de subarray positief zijn. Als een subarray een som heeft die groter is dan de gegeven som dan is er geen mogelijkheid dat het toevoegen van elementen aan de huidige subarray gelijk zal zijn aan de gegeven som. Het idee is dus om een ​​vergelijkbare aanpak te gebruiken als a schuifraam .

• Begin met een lege subarray.
• voeg elementen toe aan de subarray totdat de som kleiner is dan X (gegeven som) .
• Als de som groter is dan X , verwijder elementen uit de begin van de huidige subarray.

4. Kleinste venster dat alle tekens van de string zelf bevat:

Benadering:

In principe wordt een venster met karakters onderhouden door namelijk twee pointers te gebruiken begin En einde . Deze begin En einde Aanwijzers kunnen worden gebruikt om de grootte van het venster respectievelijk te verkleinen en te vergroten. Telkens wanneer het venster alle tekens van een bepaalde string bevat, wordt het venster vanaf de linkerkant verkleind om extra tekens te verwijderen en wordt de lengte ervan vergeleken met het kleinste venster dat tot nu toe is gevonden.
Als er in het huidige venster geen tekens meer kunnen worden verwijderd, beginnen we de grootte van het venster te vergroten met behulp van de einde totdat alle verschillende karakters die in de string aanwezig zijn, ook in het venster aanwezig zijn. Zoek ten slotte de minimale grootte van elk venster.

Oefenproblemen bij de schuifraamtechniek:

Gerelateerde artikelen:

• R recente artikelen over schuifraamtechniek
• Oefenvragen over het schuifraam
• DSA in eigen tempo – De meest gebruikte en vertrouwde cursus over DSA