C语言中的窗口滑动技术

循环几乎是每个复杂问题的一部分。太多的循环/嵌套循环会增加所需的时间，从而增加程序的时间复杂性。窗口滑动技术是一种计算技术，用于减少程序中使用的嵌套循环的数量，通过用单个循环代替嵌套循环来提高程序的效率。

如果你熟悉计算机网络中的滑动窗口协议，这种技术也很类似。本教程通过不同的例子解释了这种技术的使用方法。

一般来说，当我们使用这样的嵌套循环时 。

for(i = 1; i <= n; i++)
{
    for(j = i; j < k; j++)
    {
    }
}

迭代。

外循环执行n次；每执行一次外循环，内循环就执行（k-i）次。执行整个循环所需的平均时间大约为O(N2) 。因此，开发人员不建议使用循环。

让我们举一个例子来清楚地理解这个概念 。

假设我们要找到一个数组中’k’个连续元素的最大和。用户将提供k的值。

首先，如果我们使用传统的方法，对于数组中的每个元素i，我们将从i+1到n-1遍历数组，其中n是数组的大小。我们需要对每个元素都这样做，然后比较总和，得到最大总和。

Naďve Brute force方法。

#include<stdio.h>
int main()
{
    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", size, max);
}

输出。

Enter the size of the array: 7
Enter the elements of the array: 9 2 7 9 4 2 8
Enter the size of the sub-array: 3
The maximum sum of 3 consecutive elements of the array: 20

现在，滑动窗口技术来了 。

这里的概念是，我们创建一个大小为k的窗口，我们将通过一个单位指数不断地滑动它。在这里，窗口并不是什么技术术语。我们不是像在循环中那样使用一个单一的值，而是在每次迭代中同时使用多个元素。

比如说

给定一个大小为10的数组 。

C语言中的窗口滑动技术

假设我们需要3个连续索引的最大和，创建一个3个大小的窗口，并在整个数组中不断滑动（遍历）它。这里有一个象形的表示。

迭代1 。

C语言中的窗口滑动技术

迭代2 :

C语言中的窗口滑动技术

迭代3 。

C语言中的窗口滑动技术

迭代4 。

C语言中的窗口滑动技术

迭代5 。

C语言中的窗口滑动技术

迭代6 。

C语言中的窗口滑动技术

迭代7 。

C语言中的窗口滑动技术

迭代8 。

C语言中的窗口滑动技术

使用这种方法，将没有内循环，一个单循环的迭代次数将是（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", 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;
    for(i = k; i < n; i++)
    {
        sum += a[i] - a[i - k]; /*subtract the first element of the previous window and add the next index*/
        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