介绍

滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。 滑动窗口主要应用在数组和字符串上。

可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。

滑动窗口算法更多的是一种 思想 ，而非某种数据结构的使用。

原理

伪代码

固定窗口

//固定窗口大小为 k
string s;
//在 s 中寻找窗口大小为 k 时的所包含最大元音字母个数
int right = 0;
while(right <s.size()) {
  window.add(s[right]);
  right++;
  //如果符合要求，说明窗口构造完成，
  if (right>=k) {
     //这是已经是一个窗口了，根据条件做一些事情
     //... 可以计算窗口最大值等 
    //最后不要忘记把 right -k 位置元素从窗口里面移除
  }
}
return res;

弹性窗口

string s, t;
//在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res =s;

while(right <s.size()) {
    window.add(s[right]);
    right++;
    //如果符合要求，说明窗口构造完成，移动 left 缩小窗口
    while(window 符合要求) {
        //如果这个窗口的子串更短，则更新 res
        res=minLen(res, window);
        window.remove(s[left]);
        left++;
    }
}
return res;

实现

JavaScript

/**
* Sliding Window:
* This pattern involve creating a window which can either be
* an array or numbers from one position to another.
*
* Depending on a certain condition, the window either increases
* or closes (and a new window is created).
*
* Very useful for keeping track of a subset of data in an
* array/string etc.
*
* Time Complexity: Best - O(n);
*
* Examples:
* maxSubarraySum([1,2,5,2,8,1,5],2) // returns 10
* maxSubarraySum([1,2,5,2,8,1,5],15) // returns null
* maxSubarraySum([5,2,6,9],3) // returns 17
 * @param {[Int]} arr - An array of integers on which we will perform the test.
 * @param {Int} num - An integer that displays the size of the window you want to check.
 * @returns {Int / Null} - Returns a total of N consecutive numbers or null
 */

function slidingWindow (arr, num) {
  // Edge Case:
  // If the length of the array shorter than the window size (num) return null.
  if (arr.length < num) return null
  // The highest amount of consecutive numbers
  let maxSum = 0
  // Temp amount of consecutive numbers - For comparative purposes
  let tempSum = 0
  // loop over the array {num} times and save their total amount in {maxSum}
  for (let i = 0; i < num; i++) {
    maxSum += arr[i]
  }
  // initialize {tempSum} to {maxSum}.
  tempSum = maxSum
  // loop over the array n times
  for (let i = num; i < arr.length; i++) {
    // Add the next num in the array and remove the first one
    tempSum = tempSum - arr[i - num] + arr[i]
    // save the largest number between {maxNum} and {tempNum} in maxSum.
    maxSum = Math.max(maxSum, tempSum)
  }
  return maxSum
}

参考

• 滑动窗口算法基本原理与实践 (opens new window)