学习文章：C语言中的窗口滑动技术
- C语言中的窗口滑动技术
循环几乎是每个复杂问题的一部分。太多的循环/嵌套循环会增加所需的时间，从而增加程序的时间复杂性。窗口滑动技术是一种计算技术，用于减少程序中使用的嵌套循环的数量，通过用单个循环代替嵌套循环来提高程序的效率。
如果你熟悉计算机网络中的滑动窗口协议，这种技术也很类似，本教程通过不同的例子解释了这种技术的使用方法。
一般来说，当我们使用这样的嵌套循环时 。
for(i = 1; i <= n; i++)
{
for(j = i; j < k; j++)
{
}
}
迭代： 外循环执行\(n\)次；每执行一次外循环，内循环就执行\(（k-i）\)次。执行整个循环所需的平均时间大约为$O(N^2) $。因此，开发人员不建议使用循环。
让我们举一个例子来清楚地理解这个概念 。
假设我们要找到一个数组中\(’k’\)个连续元素的最大和，用户提供\(k\)值：
首先，如果我们使用传统的方法，对于数组中的每个元素\(i\)，我们将从\(i+1\)到\(n-1\)遍历数组，其中\(n\)是数组的大小，我们需要对每个元素都这样做，然后比较总和，得到最大总和。
- 暴力方法
#include<stdio.h>
int main()
{
/*
找到一个数组中’k’个连续元素的最大和
*/
int n, size, sum=0, max = 0, j;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n], i;
printf("Enter the elements of the array: ");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the size of sub-array: ");
scanf("%d", &size);
for(i = 0; i < (n - size) + 1; i++)
{
/*
其实也是滑动窗口的思想
*/
sum = 0;
for(j = i; j < i + size; j++)
{
sum = sum + arr[j];
}
if(sum > max)
{
max = sum;
}
}
printf("The maximum sum of %d consecutive elements of the array: %d\n", size, max);
}
输出 ：
Enter the size of the array: 10
Enter the elements of the array: 8 2 1 7 3 2 5 8 1 3
Enter the size of the sub-array: 3
The maximum sum of 3 consecutive elements of the array: 20
现在，滑动窗口技术来了
这里的概念是，我们创建一个大小为\(k\)的窗口，我们将通过一个单位指数不断地滑动它。在这里，窗口并不是什么技术术语。我们不是像在循环中那样使用一个单一的值，而是在每次迭代中同时使用多个元素。
比如说给定一个大小为10的数组：
假设我们需要3个连续索引的最大和，创建一个3个大小的窗口，并在整个数组中不断滑动（遍历）它。这里有一个形象的表示。
迭代1：
迭代2 :
迭代3：
迭代4：
迭代5：
迭代6：
迭代7：
迭代8：
- 使用这种方法，将没有内循环，一个单循环的迭代次数将是\((n – k + 1)\)，在这种情况下是8。
- 所以，滑动窗口是一种用于减少嵌套循环的技术，用一个单循环代替它，以减少总的时间复杂性。
- 请注意，在每次迭代中，当窗口滑动到下一个索引时， 我们都会删除前一个窗口的第一个元素，并添加一个新的元素，即下一个继任索引。
下面是代码：
#include <stdio.h>
int maxsum(int a[], int k, int n);
int main()
{
int n, i, k;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements: ");
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the value of k: ");
scanf("%d", &k);
int max = maxsum(arr, k, n);
printf("The maximum sum of %d consecutive elements in the array: %d\n", k, max);
}
int maxsum(int a[], int k, int n)
{
int i, sum, maxm = 0;
for (i = 0; i < k; i++)
{
maxm = maxm + a[i]; //记录第一个窗口元素和
}
sum = maxm; //初始化sum
for (i = k; i < n; i++)
{
sum += a[i] - a[i - k]; //当窗口滑动到下一个索引时， 我们都会删除前一个窗口的第一个元素，并添加一个新的元素
if (sum > maxm)
{
maxm = sum;
}
}
return maxm;
}
输出：
Enter the size of the array: 10
Enter the elements: 8 2 1 7 3 2 5 8 1 3
Enter the value of k: 3
The maximum sum of 3 consecutive elements in the array: 15
- 暴力方法在两个嵌套循环中需要\(O(k*n)\)时间。
- 通过使用滑动窗口技术，时间复杂度降低到\(O(n)\)。
以下是将该技术应用于手头任何问题的步骤：
- 首先，我们必须看到，窗口的大小是恒定的，不应该改变。我们可以只对这样的问题使用该技术。
- 在确保窗口大小没有变化后，计算第一个窗口的结果，与数组其他部分的计算结果进行比较。
- 现在，用一个循环来逐个滑动窗口的索引，直到最后，不断更新所需的值。