C 语言滑动窗口技术

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

如果您熟悉计算机网络中的滑动窗口协议，这种技术是相似的。本教程将通过不同的示例解释如何使用此技术。

通常，当我们使用这样的嵌套循环时

迭代

外层循环执行 n 次；每次外层循环执行时，内层循环都会执行 (k-i) 次。执行整个循环所需的平均时间大约是 O(N²)。因此，开发人员不建议使用循环。

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

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

首先，如果我们使用朴素方法，对于数组中的每个元素 i，我们将从 i + 1 迭代数组直到 n - 1，其中 n 是数组的大小。我们需要对每个元素执行此操作并比较和以获得最大和。

朴素暴力方法

输出

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 的数组

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

第一次迭代

第二次迭代

第三次迭代

第 4 次迭代

迭代 5

第 6 次迭代

第 7 次迭代

第 8 次迭代

• 使用这种方法，将没有内层循环，并且单个循环的迭代次数将是 (n - k + 1)，在这种情况下是 8。
• 因此，滑动窗口是一种用于减少嵌套循环使用并用单个循环替换它以减少总时间复杂度的技术。
• 请注意，在每次迭代中，当窗口滑动到下一个索引时，**我们从前一个窗口中删除第一个元素，并添加一个新元素，即下一个后续索引。**

这是代码

输出

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)。

以下是将该技术应用于任何问题的步骤

1. 首先，我们必须看到窗口大小是恒定的，不应改变。我们只能将该技术用于此类问题。
2. 确保窗口大小不变后，计算第一个窗口的结果以与数组其余部分的计算进行比较。
3. 现在，使用循环将窗口逐个索引地滑动到末尾，并不断更新所需的值。