滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”，“连续子数组 xxxx”，就应该可以想到滑动窗口。

时间复杂度一般是 O(N + K) K是窗口大小

从类型上说主要有：

  • 固定窗口大小
  • 窗口大小不固定，求解最大的满足条件的窗口
  • 窗口大小不固定，求解最小的满足条件的窗口

固定窗口

例如：

可变窗口

例如：1004. 最大连续1的个数 III

1
2
3
4
5
6
7
8
9
10
11
12
13
public int longestOnes(int[] A, int K) {
        int res = 0;
        int l = 0, r = 0,count = 0;
        while(r<A.length){
            count += A[r] == 0 ? 1 : 0;
            while(count > K){
                count -= A[l++] == 0 ? 1 : 0;
            }
            res = Math.max(res,r-l+1);
            r++;
        }
        return res;
    }