窗口滑动技术-yiteyi-C++库

该技术展示了如何将某些问题中的嵌套for循环转换为单个for循环，以降低时间复杂度。让我们从一个问题开始，说明我们可以在哪里应用这种技术——

null

Given an array of integers of size ‘n’.Our aim is to calculate the maximum sum of ‘k’ consecutive elements in the array.Input  : arr[] = {100, 200, 300, 400}         k = 2Output : 700Input  : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}         k = 4 Output : 39We get maximum sum by adding subarray {4, 2, 10, 23}of size 4.Input  : arr[] = {2, 3}         k = 3Output : InvalidThere is no subarray of size 3 as size of wholearray is 2.

那么，让我们用 暴力手段 .我们从第一个索引开始，到 第k位 要素我们对所有可能的连续块或k元素组都这样做。这种方法需要嵌套for循环，外部for循环从k个元素块的起始元素开始，内部或嵌套循环将相加，直到第k个元素。

考虑下面的实现：

C++

                         // O(n*k) solution for finding maximum sum of                       
                         // a subarray of size k                       
                         #include <bits/stdc++.h>                       
                         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;                       
                         }                       

JAVA

                         // Java code here                       
                         // 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  prerna saini.                       

Python3

                         # code                       
                         import                                     sys                       
                         print                                     (                                     "GFG"                                     )                       
                         # 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#

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

PHP

                         <?php                       
                                                 // code                       
                         ?>                       
                         <?php                       
                         // O(n*k) 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                                     )                       
                         {                       
                                   
                                                 // Initialize result                       
                                                 $max_sum                                     = PHP_INT_MIN ;                       
           
                                                 // Consider all blocks                       
                                                 // starting with i.                       
                                                 for                                     (                                     $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.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // O(n*k) 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){                       
                                                 // Initialize result                       
                                                 let max_sum = Number.MIN_VALUE;                       
           
                                                 // Consider all blocks starting with i.                       
                                                 for                                     (let i = 0; i < n - k + 1; i++) {                       
                                                 let current_sum = 0;                       
                                                 for                                     (let 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                       
                         let arr = [ 1, 4, 2, 10, 2, 3, 1, 0, 20 ];                       
                         let k = 4;                       
                         let n = arr.length;                       
                         document.write(maxSum(arr, n, k));                       
           
                         </script>                       

输出

从上面的代码可以看出，时间复杂度是 O（k*n） 因为它包含两个嵌套循环。

窗口滑动技术

可以用总线中的窗格最好地理解该技术，考虑长度窗口。 N 还有固定在里面的长窗格 K 考虑一下，最初窗格是在极左，即从左边的0个单位。现在，将窗口与大小为n的数组arr[]关联，将窗格与大小为k的元素的当前_和关联。现在，如果我们对窗户施力，使它向前移动一个单位距离。窗格将覆盖下一页 K 连续元素。考虑数组 arr[] ={5,2，-1,0,3}和 K =3和 N = 5 应用滑动窗口技术 :

我们使用线性循环计算n项中前k个元素的和，并将其存储在变量窗口_sum中。
然后，我们将在阵列上线性吃草，直到到达末端，同时跟踪最大和。
要获得k个元素块的当前和，只需从前一个块中减去第一个元素，然后将当前块的最后一个元素相加。

下面的图示将清楚地说明窗口是如何在阵列上滑动的。这是我们从索引0开始计算初始窗口和的初始阶段。在这个阶段，窗口总数是6。现在，我们将最大_和设置为当前_窗口，即6。

图片[1]-窗口滑动技术-yiteyi-C++库

现在，我们按单位索引滑动窗口。因此，现在它从窗口中丢弃5，并向窗口中添加0。因此，我们将通过减去5，然后再加0得到新的窗口和。所以，我们的窗口和现在变成了1。现在，我们将比较这个窗口和最大值。由于它较小，我们不会改变最大值。

图片[2]-窗口滑动技术-yiteyi-C++库

同样地，现在我们再次将窗口滑动一个单位索引，得到新的窗口和为2。我们再次检查当前窗口和是否大于到目前为止的最大值。再一次，它更小，所以我们不改变最大值。因此，对于上面的数组，我们的最大_和是6。

图片[3]-窗口滑动技术-yiteyi-C++库

上述描述的代码：

C++

                         // O(n) solution for finding maximum sum of                       
                         // a subarray of size k                       
                         #include <iostream>                       
                         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

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

Python3

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

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

PHP

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

Javascript

                         // Javascript code for                       
                         // O(n) solution for finding                       
                         // maximum sum of a subarray                       
                         // of size k                       
                         function                                     maxSumofK(arr, k) {                       
                         let max = 0;                       
                         let sum = 0;                       
                         //find initial sum of first k elements                       
                         for                                     (let n = 0; n <  k ; n++) {                       
                                                 sum +=  arr[n];                       
                         }                       
                         //iterate the array once and increment the right edge                       
                                                 for                                     (let i = k; i < arr.length; i++) {                       
                                                 sum += arr[i] - arr[i-k];                       
                                                 //compare if sum is more than max, if yes then replace max with new sum value                       
                                                 if                                     (sum > max) {                       
                                                 max = sum;                       
                                                 }                       
                                                 }                       
                                                 return                                     max;                       
                         }                       
           
                         let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20 ];                       
                         console.log(maxSumofK(arr, 4))                       
                         //output 28                       

输出

很明显，时间复杂度是线性的，因为我们可以看到代码中只运行一个循环。因此，我们的时间复杂性是 O（n） . 我们可以使用此技术来查找最大/最小k子阵列、异或、乘积、和等。请参阅滑动窗口问题对于这样的问题。 https://youtu.be/9-3BXsfrpbY?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p

本文由 卡尼卡·塔克拉尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章