C++ 滑动窗口算法

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

滑动窗口技术

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

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

滑动窗口技术的应用示例

示例

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

我们通过添加大小为 4 的子数组 {4, 2, 10, 23} 来获得最大和。

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

朴素方法

现在让我们使用暴力方法 来分析这个问题。我们从第一个索引开始，递增到第 k 个元素。每组 k 个项目或块（可以相互跟随）都这样做。这种方法的嵌套 for 循环中的内部 或嵌套 循环将相加直到第 k 个元素。外部 for 循环从 k 个项目块中的第一个项目开始。

思考以下应用

输出

34

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

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

使用滑动窗口方法

我们使用线性循环 计算 n 个项中前 k 个项的和，并将结果存储在变量 window sum 中。然后，我们将在数组中线性遍历，直到它到达末尾，同时持续跟踪最大和。

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

窗口在数组上移动，如下图所示。

输出

34

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