滑动窗口可以归类为快慢指针，一快一慢两个指针前后相随，中间的部分就是窗口。
滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组。

滑动窗口框架概览

如果使用暴力解法，需要嵌套for循环实现穷举所有子数组，时间复杂度是N^2

1
2
3
4
5
for (int i = 0; i < nums.length; i++) {
    for (int j = i; j < nums.length; j++) {
        // nums[i, j] 是一个子数组
    }
}

如果使用滑动框架，简单的来说就是维护一个窗口，不断滑动，然后更新答案

1
2
3
4
5
6
7
8
9
10
11
12
13

int left , right = 0;
while (right <nums.size()){
    // 增大窗口
    window.addLast(nums[right]);
    right ++;
    while(window needs shrink){
        // 缩小窗口
        window.removeFirst(nums[left]);
        left++;
    }
}

基于滑动窗口框架写出的代码时间复杂度是O(N)

  • 滑动窗口伪代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 滑动窗口算法伪码框架
def slidingWindow(s: str):
    # 用合适的数据结构记录窗口中的数据，根据具体场景变通
    # 比如说，我想记录窗口中元素出现的次数，就用 map
    # 如果我想记录窗口中的元素和，就可以只用一个 int
    window = ...

    left, right = 0, 0
    while right < len(s):
        # c 是将移入窗口的字符
        c = s[right]
        window.add(c)
        # 增大窗口
        right += 1
        # 进行窗口内数据的一系列更新
        ...

        # *** debug 输出的位置 ***
        # 注意在最终的解法代码中不要 print
        # 因为 IO 操作很耗时，可能导致超时
        # print(f"window: [{left}, {right})")
        # ***********************

        # 判断左侧窗口是否要收缩
        while left < right and window needs shrink:
            # d 是将移出窗口的字符
            d = s[left]
            window.remove(d)
            # 缩小窗口
            left += 1
            # 进行窗口内数据的一系列更新
            ...

__END__