动画算法：滑动窗口，高效率的解决数组问题

滑动窗口是一种编程技巧，用于把多层嵌套循环平铺成单层循环，来减少时间复杂度。几年前微软中国曾经考察过这项能力。那么这个视频我们来看一下滑动窗口的实现方法。

假设有一个题目：

信息

给定一个数组，有 5 个元素，分别是 [3, 2, -4, 6, 1]，对于每 3 个连续的元素，求它们最大的和。

例如，对于这个数组，前 3 个元素 3, 2, -4, 和为 1，后面 2, -4, 6 和为 4，再后面 -4, 6, 1 和为 3，因此最大的和是 4。

如果使用最简单的暴力解题方式，我们可能会用双层循环：

• 从第一个元素开始遍历，直到倒数第 3 个。
• 然后再内层循环中，加上后面 2 个元素的值。
• 之后比对最大的和。循环结束之后就得到了结果。

function burteForce(arr, windowSize) {
  if (arr.length < windowSize) {
    return null;
  }

  let maxSum = 0;
  for (let i = 0; i < arr.length - windowSize + 1; i++) {
    let tempSum = 0;
    for (let j = 0; j < windowSize; j++) {
      tempSum += arr[i + j];
    }
    maxSum = Math.max(maxSum, tempSum);
  }

  return maxSum;
}

这样的效率会比较低，因为对于每个元素，都要在内层循环中循环 3 次，如果计算更多的元素，那么就要循环更多次。

使用滑动窗口算法可以提高速度，我们用 k 表示要计算的连续的元素数量，例如这个示例里边 k = 3，它的原理是：

• 先计算前 k 个连续的元素的和。
• 把和保存到一个变量 maxSum 当前最大值中。再定义一个变量 tempSum 保存后面计算 k 个元素的和，用于和当前最大值进行比对。
• 之后，我们把 k 个元素当成可视区域窗口，让它整体向右移动 1 位，来计算后面 k 个元素的和。
• 这样计算的话，就是减掉之前窗口所在位置中第 1 个元素的值，再加上窗口新位置中，最后一个元素的值。
• 接下来比对新的窗口的和 tempSum 和 maxSum，如果 tempSum 大于 maxSum 就更新当前最大值。
• 重复第 3 步和后面的操作，直到达到数组的末尾就找到了最大的和。

这个是 JavaScript 代码实现：

function slidingWindow(arr, windowSize) {
  if (arr.length < windowSize) {
    return null;
  }

  let maxSum = 0;
  let tempSum = 0;

  for (let i = 0; i < windowSize; i++) {
    maxSum += arr[i];
  }

  tempSum = maxSum;
  for (let i = windowSize; i < arr.length; i++) {
    tempSum = tempSum - arr[i - windowSize] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }

  return maxSum;
}

小结

好了，这个就是使用滑动窗口解题的过程，你学会了吗？如果有帮助请三连并关注，想学更多的开发知识，可以在评论区留言，感谢观看！