滑动窗技术

可以以不同方式应用此技术。它可以应用于字符串，也可以应用于整数。以下是我们可以应用此技术的2种方法。

1.固定大小的窗口[我们将在本章中研究的这项技术]：这里将为您提供一个数组和一个固定大小的窗口，您需要在该固定窗口中找到具有最大值的最大连续子数组。

2.可变大小窗口：这里将为您提供一个数组和一个数字，您需要找到任意长度的子数组，以找到将这个数字相加的连续元素。

如上所述，为您提供了一个数组和窗口大小。您需要找到一个具有该窗口大小的连续子数组。

例如：

数组= [1、2、4、3、5、7、6]

视窗大小= 2

因此，通过查看数组，我们可以看到窗口大小为2的[7，6]在该固定窗口中具有最大值的最大连续子数组。

我们可以通过蛮力法解决上述问题。即以2为循环。第一个循环将从第一个索引开始，然后在内部循环中将遍历该索引中的所有元素，直到窗口大小为止。在这里，时间复杂度将为O（n ^ 2）。这可以通过滑动窗口技术进一步改善。

通过使用隔离窗口，我们可以将复杂度降低到O（n）。

步骤1：计算前k个数字的总和。

步骤2：移至下一个元素，然后计算其总和。如果当前总和大于先前总和，则更新最大值，否则保留先前的值。

步骤3：继续执行步骤2，直到到达数组末尾。

使用示例了解滑动窗口技术：

[1、2、4、3、5、7、6]

[1, 2]

[2, 4]

[4, 3]

[3, 5]

[5, 7]

[7，6] = 13是最大值。

从上面可以看到，我们将值从一个元素滑到另一个元素。因此，我们称其为滑动窗口方法。

#include <iostream> 
using namespace std; 
  
void sliding_window(int arr[], int n, int k) 
{ 
    int max_sum = 0; 
    
    //calculte the value for the first window
    for (int i = 0; i < k; i++) 
        max_sum += arr[i]; 
  
    int current_sum = max_sum; 

    //from the next element, calcute if there is any 
    //sub array that has max value
    for (int i = k; i < n; i++) 
    { 
        current_sum += arr[i] - arr[i - k]; 
        max_sum = max(max_sum, current_sum); 
    } 
    
    cout<<"The max sum using sliding window is "<<max_sum<<endl; 
    return ;
} 
  
int main() 
{ 
    int arr[] = { 1, 2, 4, 3, 5, 7, 6 }; 
    
    int k = 2; 
    
    sliding_window(arr, 7, k); 
    
    return 0; 
}

 

输出量

The max sum using sliding window is 13

在所有情况下，滑动窗口技术的时间复杂度均为O（n）[线性时间]。

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。