C++ 滑动窗口算法

滑动窗口技术是一种计算方法，旨在用单个循环替代嵌套循环，以减少时间复杂度。

滑动窗口技术

让我们用一个类比来帮助我们理解这个策略。考虑一个固定在长度为n的窗口内的窗格。

将窗口中的n个元素数组arr[]与窗格中的k个当前和组合在一起，窗格在其起始位置（即距离左边0个单位）时，窗口将移动一个单位距离。窗格将覆盖接下来的k个组件。

应用滑动窗口技术的示例

示例：

给定一个大小为n的整数数组，我们的目标是获得数组前k个成员的最大和。

Input  :arr[] = {100, 200, 300, 400}, k = 2
Output : 700

Input  :arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Output : 39

通过将大小为 4 的子数组{4, 2, 10, 23}相加，我们得到最大的总和。

Input  :arr[] = {2, 3}, k = 3
Output : Invalid

没有大小为 3 的子数组，因为整个数组的大小是 2 。

原生法

让我们使用 暴力法 分析一下这个问题。我们从第一个索引开始，增加到第 k 个元素。可以相互跟随的 k 项或块的每个组都可以完成。该方法嵌套的嵌套 for 循环将添加到第 k 个元素。块中的 k 项的第一项是外部for循环的开始处。

思考以下应用：

#include 
using namespace std;

int maxSum(int arr[], int n, int k)
{
int maximum_sum = INT_MIN;
for (int i = 0; i < n - k + 1; i++) {
int curr_sum = 0;
for (int j = 0; j < k; j++)
curr_sum = curr_sum + arr[i + j];
maximum_sum = max(curr_sum, maximum_sum);
}
return maximum_sum;
}
int main()
{
int arr[] = { 11, 6, 7, 10, 6, 3,11, 0, 20 };
int k = 4;
int n = sizeof(arr) / sizeof(arr[0]);
cout<

输出

从上面的代码可以看出，它有两个嵌套循环，时间复杂度为O(k*n)。

考虑一个长度为n的窗口，其中一个固定长度为k的窗格，以更好地理解滑动窗口技术。要注意的是，窗格最初在最左边，即距离左边0个单位。现在，将窗口与n个元素数组arr[]和k个元素当前和的窗格相关联。如果我们现在对窗口施加力，它将向前移动一个单位的距离。下一个k个元素将被窗格覆盖。

使用滑动窗口方法

我们使用线性循环来计算前n个元素中的前k个元素的和，并将结果存储在变量window sum中。然后，同时跟踪最大和，我们将在数组线性扫描到达末尾之前进行遍历。

只需将当前块的最后一个元素加到前一个块的第一个元素上，即可获得k个元素块的当前总和。

窗口在数组上移动的示例如下所示。

#include 
using namespace std;
int maxSum(int arr[], int n, int k)
{
if (n < k) {
cout<< "not valid";
return -1;
}
int maximum_sum = 0;
for (int i = 0; i < k; i++)
maximum_sum += arr[i];
int window_sum = maximum_sum;
for (int i = k; i < n; i++) {
window_sum += arr[i] - arr[i - k];
maximum_sum = max(maximum_sum, window_sum);
}
return maximum_sum;
}
int main()
{
int arr[] = { 11, 6, 7, 10, 6, 3,11, 0, 20  };
int k = 4;
int n = sizeof(arr) / sizeof(arr[0]);
cout<

输出

现在我们可以看到我们的代码只有一个循环，很清楚的可以看出 时间复杂度 是线性的。因此， 时间复杂度 是 O(n) 。