滑动窗口技术🔥

嘿，好奇的朋友们👋！你是否曾经因为编写了一个不仅能解决问题而且效率极高的算法而感到如此兴奋？在这篇博客中，我们将学习一种能让你更频繁地体验这种感觉的算法！滑动窗口技术 (SWT) - 我理解这种算法有助于将解决方案的时间复杂度（通常用于处理数组等顺序和可迭代数据结构的问题）从 O(N²) 提升到 O(N)。如果你不理解时间复杂度，只需知道它有助于改进你的解决方案，使其运行速度更快即可。

什么是 SWT？

根据大多数定义，SWT 是一种将一些蛮力（主要是 O(N²)）算法转换为线性（O(N)）算法的方法。

有帮助吗？

在面试中，将算法从 O(N²) 改进到 O(N) 是一件很有意义的事情（嗯...至少对我来说😅）。

怎么做？

为了理解如何做到这一点，让我们看一个问题，首先我们将考虑一个蛮力解决方案，然后通过应用 SWT 对其进行改进。在此之前，让我先向您介绍一下我们如何应用 SWT（现在这可能没有意义，但在解决问题时肯定会有意义！）。
假设我们有一个数组，并且想要找到数组中的最大元素。解决方案可能是查看每个元素并跟踪最大元素。用 SWT 的方式来说，它可能看起来像这样：👇 现在你可能已经猜到了，窗口从左向右滑动（它点击了吗？💡），我们查看值检查它是否是我们见过的最大元素，并一直持续到窗口到达数组末尾。窗口可以是任意大小，具体取决于我们要处理的问题，它可以是一个（或任意数量的元素）元素长，也可以是可变大小。窗口大小可以是固定的，也可以是动态的。

问题

给定一个包含 N 个正整数的数组，求出 3 个连续元素的最大和

暴力破解方法

我想到的第一个解决方案是找出所有可能的包含 3 个连续元素的子数组，求它们的和，并记录其中的最大值。我们需要两个嵌套循环来实现这个目标，我们来看看代码中的算法。

let arr = [1, 3, 5, 6, 2, 7, 8];
let maxSum = 0;  //to keep track of maximum sum.

for (let i = 0; i < arr.length - 3 + 1; i++){
  //Initializing sum
  let sum = 0;
  //Adding 3 elements starting from i
  for (let j = 0; j < 3; j++){
    sum = sum + arr[i + j];
  }
  //Storing the maximum sum
  maxSum = Math.max(sum,maxSum);
}

console.log(maxSum);

该算法的时间复杂度为 O(N*3)，如果元素集大于 3，则可能会更糟。

SWT 方法

现在，让我们看看 SWT 方法如何工作。

现在我们想要创建一个大小为 3 的窗口，计算它的和，并在窗口向右滑动时跟踪最大和。现在让我们想象一下，如果窗口向右移动一个元素会发生什么。我们实际上做的是将第 4 个元素添加到和中，并减去第一个元素，然后重复此操作，直到窗口到达数组的末尾。让我们看看代码中是如何实现的。

let arr = [1, 3, 5, 6, 2, 7, 8];
let maxSum = 0;  //to keep track of maximum sum.
let sumOfWindow = 0; //to keep track of sum of the window.
let windowSize = 0;

for (let i = 0; i < arr.length + 1; i++){
  if(windowSize == 3){
    console.log('current windows sum is');
    console.log(sumOfWindow);
    //storing the maximum sum
    maxSum = Math.max(maxSum, sumOfWindow);
    //deleting the end element of the window
    sumOfWindow = sumOfWindow - arr[i - 3];
    windowSize--;
  }

   //adding elements to the window.
  sumOfWindow = sumOfWindow + arr[i];
  windowSize++;

}

console.log("The maximum sum is: " + maxSum);

瞧！这只需要一个循环，时间复杂度就达到了 O(N)！咳咳……To use fewer loops, use more brain可能还需要几行代码（不一定）。
就是这样Sliding Window Technique！！

何时使用它？

当我看到与可迭代数据结构（如数组或字符串）的连续元素有关的问题时，我通常会尝试使用它（例如：max continuous subarray，longest non-repeating substrings）。

既然您了解了 SWT，您会尝试在 hackerrank 中解决这个问题吗？请记住，窗口的大小可以是动态的，它并不总是必须是像三这样的固定数字。

如果您喜欢这个博客，请考虑给我买杯咖啡😊或在 patreon 上支持我。

查看本系列的其他博客。👇