滑动窗口算法

最近买了 educative.io 的会员,正在刷 Grokking the Coding Interview: Patterns for Coding Questions 这门课程,课程里总结了 16 种常见的算法题模式。刚刷完第一种类型滑动窗口,总结一下模板和题型。

滑动窗口是TCPIP协议中使用的一种算法,详情访问「这篇文章」,写的很通俗易懂。

滑动窗口算法可以用来解决数组和字符串的子元素问题,它可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。具体思想是,利用两个指针来控制窗口(子数组或子字符串)的大小,窗口的大小可以是固定的,也可以是可变长度的。窗口大小的控制以及滑动的控制条件是根据窗口内的元素值来判断的。

所以一般能用滑动窗口解决的问题有以下特点:

  1. 数据结构为数组或字符串,并且想要找的是连续的元素
  2. 窗口只能从左往右滑,也就是两个指针只能往右走,因为这个算法默认最优解在最右边。

1. 窗口大小固定题型

1
2
3
4
给一个整数数组,在其中找到固定窗口k下最大和
Input: [2, 1, 5, 1, 3, 2], k=3 
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].

暴力解法:也就是对每一个数都求固定窗口的和,找出最大值。

1
2
3
4
5
def max_sub_array_of_size_k(k, arr):
    max_sum = 0
    for i in range(len(arr)-k+1):
        max_sum = max(max_sum, sum(arr[i:i+k]))
    return max_sum

这段代码的时间复杂度是O(N*K),N是数组长度,K是窗口大小。数组内的一个元素会被计算好几次,明显有点浪费。这里用滑动窗口算法的话,就能把时间复杂度压到O(N)。每次移动窗口把右边的值加上,把左边的值减掉。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def max_sub_array_of_size_k(k, arr):
    max_sum, window_sum, window_start = 0, 0, 0

    for window_end, n in enumerate(arr):
        # 加右边
        window_sum += arr[window_end]
        # 如果窗口大了,左边往右移
        if window_end-window_start+1 > k:
            window_sum -= arr[window_start]
            window_start += 1

        max_sum = max(max_sum, window_sum)

    return max_sum

2. 窗口大小变化题型

1
2
3
4
给一个整数数组和一个目标值, 找到和大于目标值的最小连续子数组。
Input: [2, 1, 5, 2, 3, 2], S=7 
Output: 2
Explanation: The smallest subarray with a sum greater than or equal to '7' is [5, 2].

这题比较难的是需要找到最小子数组,思路就是当窗口的数组和大于目标值时,左边的窗口往右滑,看看减掉左边的值,能否继续大于目标值,一直尝试到当前窗口的数组和小于目标值为止。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def smallest_subarray_with_given_sum(s, arr):
    min_len, window_sum, window_start = float('inf'), 0, 0

    for window_end, n in enumerate(arr):
        window_sum += n

        while window_sum >= s:
            min_len = min(min_len, window_end-window_start+1)
            window_sum -= arr[window_start]
            window_start += 1
        
    if min_len == float('inf'):
        return 0
    return min_len

3. 最长子字符串问题

1
2
3
4
给一个字符串和一个K 找到不同字符数不大于K的最长子字符串
Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".

思路就是创建一个记录当前窗口字符的频次的dict,每当向右移的时候,判断当前窗口不同字符字符数是否大于K,大于K的话左移直到满足条件。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def longest_substring_with_k_distinct(str1, k):
  # TODO: Write your code here
  max_len = window_start = 0
  from collections import defaultdict
  freq = defaultdict(int)

  for window_end, c in enumerate(str1):
    freq[c] += 1

    while len(freq) > k:
      start_c = str1[window_start]
      freq[start_c] -= 1
      if freq[start_c] == 0:
        del freq[start_c]
      window_start += 1

    max_len = max(max_len, window_end-window_start+1)
  
  return max_len

4. 总结

滑动窗口算法的抽象思想为:

1
2
3
4
5
6
7
8
window_start = 0
for window_end, c in enumerate(s):
    window.add(c)

    while (condition) {
        window.remove(s[window_start])
        window_start += 1
    }


如果本文对您有帮助,欢迎打赏。

赞赏码