我认为它更多的是一种技术而不是算法。这是一种可用于各种算法的技术。
我认为通过以下示例可以最好地理解该技术。想象一下我们有这个数组：
[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]
我们如何找到五个连续元素的最大和？好吧，我们首先看看5, 7, 1, 4, 3看到总和是20。然后我们看看下一组五个连续元素，即7, 1, 4, 3, 6。这些的总和是21。这比我们之前的总和还要多，所以7, 1, 4, 3, 6目前是我们迄今为止最好的。
让我们看看是否可以改进。1, 4, 3, 6, 2？不，这总计为16. 4, 3, 6, 2, 9？总和就是24，所以现在这是我们得到的最佳序列。现在我们进入下一个序列，3, 6, 2, 9, 2。总和就是22，这并没有打败我们目前最好的24。我们已经到达了终点，所以我们已经完成了。
以编程方式实现这一点的强力方法如下：
const getMaxSumOfFiveContiguousElements = (arr) => {
let maxSum = -Infinity;
let currSum;
for (let i = 0; i <= arr.length - 5; i++) {
currSum = 0;
for (let j = i; j < i + 5; j++) {
currSum += arr[j];
}
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
};
这个的时间复杂度是多少？它是O(n*k)。外循环正在经历n - k + 1项，但是当n远大于k，我们可以忘记k + 1部分并调用它n项目。然后内循环正在经历k项，所以我们有O(n*k)。尝试像这样想象它：
我们能把这个简化为O(n)？让我们回到这个数组：
[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]
首先我们得到总和5, 7, 1, 4, 3。接下来我们需要求和7, 1, 4, 3, 6。像这样想象它，每组五个元素周围都有一个“窗口”。
第一个窗口和第二个窗口有什么区别？好吧，第二个窗口去掉了5在左边但添加了一个6在右侧。所以既然我们知道第一个窗口的总和是20，为了得到第二个窗口的总和，我们采取20，减去5，并添加6 to get 21。我们实际上不必遍历第二个窗口中的每个元素并将它们相加（7 + 1 + 4 + 3 + 6）。这将涉及重复和不必要的工作。
这里滑动窗口方法最终是两个操作而不是五个操作，因为k is 5。这并不是一个巨大的改进，但你可以想象对于更大的k（以及更大的n）这确实有帮助。
以下是使用滑动窗口技术的代码的工作方式：
const getLargestSumOfFiveConsecutiveElements = (arr) => {
let currSum = getSum(arr, 0, 4);
let largestSum = currSum;
for (let i = 1; i <= arr.length - 5; i++) {
currSum -= arr[i - 1]; // subtract element to the left of curr window
currSum += arr[i + 4]; // add last element in curr window
largestSum = Math.max(largestSum, currSum);
}
return largestSum;
};
const getSum = (arr, start, end) => {
let sum = 0;
for (let i = start; i <= end; i++) {
sum += arr[i];
}
return sum;
};
这就是滑动窗口技术的要点。在其他问题中，您可能会做一些比获取窗口内元素的总和更复杂的事情。或者窗口本身可能具有不同的大小，而不是我们在这里看到的固定大小 5。但是滑动窗口技术的基本应用应该为您提供构建的基础。
