滑动窗口算法可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

参考文章：

算法07-滑动窗⼝算法

滑动窗口算法精讲（Sliding Window Algorithm）

滑动窗口相关算法题总结

详细讲解

一句话总结

滑动窗口算法是一种通过维护一个动态窗口来解决问题的技巧，窗口在数据上“滑动”，逐步找到最优解。

核心思想

滑动窗口算法的本质是双指针法中的左右指针法，所谓滑动窗口，就像描述的那样，可以理解成是一个会滑动的窗口，每次记录下窗口的状态，再找出符合条件的适合的窗口。它可以将双层嵌套的循环问题，转换为单层遍历的循环问题。使用两个指针一左一右构成一个窗口，就可以将二维循环的问题转化成一维循环一次遍历，相当于通过旧有的计算结果对搜索空间进行剪枝，使时间复杂度从O（n²）降低至O（n），比如经典字符串查找算法Rabin-Karp 指纹字符串查找算法，它本质上也使用了滑动窗口的思想，通过公式推导降低窗口滑动时计算子串哈希值的复杂度。

滑动窗口算法更多的是一种思想或技巧，按照窗口大小是否固定分为固定滑动窗口和变长滑动窗口，可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。往往类似于“请找到满足xx的最x的区间（子串、子数组等）的xx”这类问题都可以使用该方法进行解决。

想象你在看一列火车，火车窗口只能看到一部分车厢。滑动窗口算法就是通过调整窗口的起点和终点，找到你感兴趣的部分（比如最长的连续车厢、最短的覆盖范围等）。

适用场景

滑动窗口算法通常用于解决以下问题：

  1. 子数组/子字符串问题：比如找最长的无重复字符子串、最短的覆盖子串等。
  2. 连续区间问题：比如找满足条件的连续子数组。
  3. 优化问题：比如在固定窗口大小内找最大值、最小值或平均值。

滑动窗口的两种类型

固定大小的窗口

  • 窗口大小固定，比如每次只看连续的 3 个元素。
  • 例子：计算数组中每个长度为 k 的子数组的平均值。

可变大小的窗口

  • 窗口大小不固定，根据条件动态调整。
  • 例子：找最长的无重复字符子串。

滑动窗口的基本步骤

  1. 初始化窗口：

    • 定义窗口的起点（left）和终点（right），通常初始化为 0，把索引闭区间 [left, right] 称为一个「窗口」。
    • 定义一些辅助变量（比如当前窗口的和、最大值、最小值等）。

  2. 滑动窗口：

    • 移动右边界（right），扩大窗口 [left, right]，直到满足某个条件。（找可行解）

    • 移动左边界（left），缩小窗口 [left, right]，直到不满足条件。同时每次增加 left 都要更新一轮结果。（优化可行解）

    • 在滑动过程中，记录需要的结果（比如最大长度、最小长度等）。

  3. 滑动窗口，直至一次遍历结束：重复第 2 步，直到 right 到达到的尽头。

  4. 返回结果：根据滑动过程中记录的结果，返回最终答案。

关键特点

  1. 高效：通过滑动窗口，避免了重复计算，时间复杂度通常为 (O(n))。
  2. 灵活：适用于多种问题，尤其是需要处理连续区间的问题。
  3. 双指针：滑动窗口通常用双指针（left 和 right）来实现。

模板

模板一

1
2
3
4
5
6
7
8
9
10
11
12
13
public void slideWindowTemplate(String nums){
    int l = 0, r = 0;        //[初始化窗口]
    //codes...               [其他初始化信息,定义一些维护数据的数据结构]
    while(r < nums.length){
        //codes.....         [维护窗口中的数据] 
        while(l < r && check(xxx) == false){   //[窗口不满足某种性质]
            //codes...       [维护窗口中的数据] 
            l++;             //[缩小窗口]
        }
        //codes..            [更新结果]
        r++;                 //[增大窗口]
    }
}

模板二

1
2
3
4
5
6
7
8
9
10
11
public void slideWindowTemplate(String nums){
    //codes...               [其他初始化信息,定义一些维护数据的数据结构]
    for(int l = 0, r = 0; r < nums.length; r++){
        //codes.....         [维护窗口中的数据] 
        while(l < r && check(xxx) == false){   //[窗口不满足某种性质]
            //codes...       [维护窗口中的数据] 
            l++;             //[缩小窗口]
        }
        //codes..            [更新结果]
    }
}

算法题

补种未成活胡杨

近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨(编号1-N)，排成一排。一个月后，有M棵胡杨未能成活。
现可补种胡杨K棵，请问如何补种(只能补种，不能新种)，可以得到最多的连续胡杨树?
输入描述
N 总种植数量
M 未成活胡杨数量
M 个空格分隔的数，按编号从小到大排列
K 最多可以补种的数量
其中:
1<=N<=100000
1<=M<=N
0<=K<=M
输出描述：最多的连续胡杨棵树
示例1
输入
5
2
2 4
1
输出 3
说明：补种到2或4结果一样，最多的连续胡杨棵树都是3
示例2
输入
10
3
2 4 7
1
输出 6
说明：补种第7棵树，最多的连续胡杨棵树为6(5,6,7,8,9,10)
解析
初始化：首先读取总种植数量N，并初始化一个长度为N的数组tree，所有初始值为0，表示所有胡杨都成活。读取未成活胡杨的数量M，然后读取未成活胡杨的编号，将相应位置的tree值设为1，表示该胡杨未成活。读取最多可以补种的数量K。

滑动窗口算法：遍历每棵树的位置，如果当前树未成活（tree[i]为1），则将其加到tot中。如果未成活树的总数tot超过K，说明当前窗口的未成活树数超过了补种数量，需要调整窗口大小，从左侧逐次减少未成活树数，直到tot不超过K。每次调整窗口之后，计算当前窗口的大小（i - j + 1），如果大于之前记录的最大连续成活树数，则更新最大值。

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
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt(); // 读入总种植数量N
    int tree[] = new int[N];  // 创建一个长度为N的数组用于存储每棵树的状态
    int m = in.nextInt(); // 读入未成活胡杨数量M
    for (int i = 0; i < m; i++) {
        int x = in.nextInt(); // 读入每棵未成活胡杨的编号
        tree[x - 1] = 1; // 将对应位置的值设为1，表示未成活
    }
    int cnt = sc.nextInt(); // 读入最多可以补种的数量K
    // 初始化变量:总未成活树数、最大连续胡杨数、滑动窗口起始位置
    int tot = 0, ans = 0, j = 0;
    // 遍历所有树的位置
    for(int l = 0, r = 0; r < n; r++) {
        // 每次遍历都将当前树的状态加到tot，如果未成活则+1，成活则+0
        tot += tree[r];
        // 如果未成活树的总数超过了补种限制
        while (tot > cnt) {
            tot -= tree[l]; // 减去窗口起始位置的树的状态
            l++;         // 滑动窗口的起始位置右移
        }
        // 计算当前滑动窗口的大小，如果比之前的最大连续数大则更新
        if (r - l + 1 > ans) {
            ans = r - l + 1;
        }
    }
    System.out.println(ans); // 输出最大连续胡杨数
}

无重复字符的最长子串

LeetCode 3 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int lengthOfLongestSubstring(String s) {
    HashMap<Character, Integer> map = new HashMap<>();
    int left = 0, max = 0;
    for (int right = 0; right < s.length(); right++) {
        if (map.containsKey(s.charAt(right)) && map.get(s.charAt(right)) >= left) {
            max = Math.max(max, right - left);
            left = map.get(s.charAt(right)) + 1; // 左边设置为重复字符的下一位
            map.put(s.charAt(right), right);// 已存在字符更新最新下标
        } else {
            map.put(s.charAt(right), right); // 添加字符 及下标
            max = Math.max(max, right - left + 1);
        }
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
int lengthOfLongestSubstring(string s) s{
    set<char> record;
    int res = 0,left = 0, right = 0;
    while(right < s.size()) {
        if(record.find(s[right]) == record.end()) {
            record.insert(s[right++]);
            res = max(res,(int)record.size());
        } else {
            record.erase(s[left++]);
        }
    }
    return res;
}

最小覆盖子串

LeetCode 76 最小覆盖子串

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入：S = “ADOBECODEBANC”, T = “ABC”
输出：“BANC”
提示：
如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public String minWindow(String s, String t) {
    int[] cnt = new int[128]; // ASCII码  0-9：48-57； a-z:97-122  A-Z：65-90
    for (int i = 0; i < t.length(); i++) cnt[t.charAt(i)]++;
    int l = 0, r = 0, ansL = 0, ansR = 0, ans = Integer.MAX_VALUE, cntT = t.length();
    while (r < s.length()) {
        if (cnt[s.charAt(r++)]-- > 0) cntT--;
        while (cntT == 0) {
            if (r - l < ans) {
                ans = r - l;
                ansL = l;
                ansR = r;
            }
            if (cnt[s.charAt(l++)]++ == 0) cntT++;
        }
    }
    return ans == Integer.MAX_VALUE ? "" : s.substring(ansL, ansR);
}

最大连续1的个数 III

LeetCode 1004 最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
1 <= A.length <= 20000
0 <= K <= A.length
A[i] 为 0 或 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int longestOnes(int[] nums, int k) {
    int left = 0, right = 0, res = 0;
    while (right < nums.length) {
        if (nums[right] == 0) {
            k--; // 0变成1，消耗一个1
        }
        while (k < 0) {
            if (nums[left] == 0) {
                k++; // 1变成0，归还一个1
            }
            left++;
        }
        res = Math.max(res, right - left + 1); // 把 right++语句在后面，所以这里是 right-left+1
        right++;
    }
    return res;
}

可获得的最大点数

LeetCode 1423 可获得的最大点数

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
示例 2：
输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
示例 3：
输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
示例 4：
输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
示例 5：
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202
提示：
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxScore(int[] cardPoints, int k) {
    int len = cardPoints.length, sum = 0;
    for (int cardPoint: cardPoints) {
        sum += cardPoint;
    }
    int min = Integer.MAX_VALUE, temp = 0;
    int length = len - k;
    for (int i = 0; i < len; i++) {
        temp += cardPoints[i];
        if (i >= length) {
            temp -= cardPoints[i - length];
        }
        if (i >= length - 1)
            min = Math.min(min, temp);
    }
    return sum - min;
}

绝对差不超过限制的最长连续子数组

LeetCode 1438 绝对差不超过限制的最长连续子数组

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
示例 1：
输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。
示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。
示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

1
2
3
4
5
6
7
8
9
10
11
12
// 滑窗+红黑树 极简解法，时间复杂度O(n*logn)
public int longestSubarray(int[] nums, int limit) {
    TreeMap<Integer, Integer> treeMap = new TreeMap<>(); // 默认升序
    int left = 0, right = 0;
    while (right < nums.length) {
        treeMap.compute(nums[right++], (k, v) -> v == null ? 1 : v + 1);
        if (treeMap.lastKey() - treeMap.firstKey() > limit) {
            treeMap.compute(nums[left++], (k, v) -> v == 1 ? null : v - 1);
        }
    }
    return right - left;
}

以下解法会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int longestSubarray(int[] nums, int limit) {
    PriorityQueue<Integer> minQueue = new PriorityQueue<>(Comparator.naturalOrder());
    PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());
    int left = 0;
    int right = 0;
    int ans = 0;
    while (right < nums.length && left < nums.length) {
        minQueue.add(nums[right]);
        maxQueue.add(nums[right]);
        if (maxQueue.peek() - minQueue.peek() <= limit) {
            ans = Math.max(ans, right - left + 1);
            right++;
            continue;
        }
        maxQueue.remove((Integer) nums[left]);
        minQueue.remove((Integer) nums[left]);
        left++;
        right++;
    }
    return ans;
}