滑动窗口算法最简单的教程（1）

滑动窗口相关问题在面试中很常见，本文目的，就是让你用最节约脑细胞的方式，掌握这个算法技巧。这是个系列教程，如果觉得好，就请关注一波吧。

1 举个栗子

下面这个问题，就是典型的滑动窗口要解决的问题。

请找出一个数组中所有大小为K的连续子数组的平均值

看起来，这句话有点绕，没关系，咱们用个具体的小例子来说明一下：

Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5

这个例子，我们需要找出大小为5的所有连续子数组的平均值，我们可以这样算：

• 对于前5个元素的子数组 (下标 0-4), 平均值是: (1+3+2+6-1)/5 => 2.2
• 第二个5个元素的子数组的平均值 (下标 1-5) 是: (3+2+6-1+4)/5 => 2.8
• 第三个5个元素的子数组 (下标 2-6), 平均值是: (2+6-1+4+1)/5 => 2.4
• ...

这样一直算下去，我们就可以得到最终的输出结果：

Output: [2.2, 2.8, 2.4, 3.6, 2.8]

2 暴力解法

我们自然想到一个暴力的解法，就是求解所有的大小为5的子数组的和，除以5得到它们的平均值。代码长这样：

def find_averages_of_subarrays(K, arr):
  result = []
  for i in range(len(arr)-K+1):
    # 求 和  接下来 'K'ts
    _sum = 0.0
    for j in range(i, i+K):
      _sum += arr[j]
    result.append(_sum/K)  # calculate average

  return result

3 问题分析

这个暴力解法有什么问题呢？问题在时间复杂度有点高。对于数组中的每个元素，咱们都需要计算它和后面的K-1个元素的和，并且求平均，如此，时间复杂度是 . 那有什么可以简化的办法呢？仔细观察可以发现，对于两个相邻的连续的大小为5的子数组，它们的重叠部分被计算了两次。在上面的具体例子中：

可以看出，第一个子数组和第二个子数组有4个重叠元素，这启发我们，在计算元素的和的时候，对于重叠部分的元素，是不是可以复用前面的子数组的计算结果呢？

4 滑动窗口

答案是YES。这就是滑动窗口算法提出的初衷，解决重复计算。我们可以把每一个连续的子数组看作一个大小为5的窗口。这样的好处是，当我们从一个子数组移到下一个子数组时，相当于是把窗口向前滑动了一个元素。此时，为了重用上一个窗口的计算求和的结果，我们只要从窗口中减去那个移出的元素，加上新移进来的元素就可以了。这样，对新的子数组，就省去了求5个元素的和的过程。如此，时间复杂度就会变成。

如图所示：

具体实现算法如下：

def find_averages_of_subarrays(K, arr):
  result = []
  windowSum, windowStart = 0.0, 0
  for windowEnd in range(len(arr)):
    windowSum += arr[windowEnd]  # 加上下一个元素
    # 移动窗口，注意，如果窗口大小还没达到K，我们就不需要移动窗口哦。
    if windowEnd >= K - 1:
      result.append(windowSum  K)  # 计算平均值
      windowSum -= arr[windowStart]  # 减去移出的元素
      windowStart += 1  # 移动窗口的头部

  return result