知识文档站

Appearance

滑动窗口

解题思路 ​

滑动窗口：维持左、右边界都不回退的一段范围，来求解很多子数组（串）的相关问题 ​

滑动窗口的关键：找到范围和答案指标之间的单调性关系（类似贪心） ​

滑动过程：滑动窗口可以用简单变量或者结构来维护信息 ​

求解大流程：求子数组在每个位置开头或结尾情况下的答案（开头还是结尾在于个人习惯） ​

注意：滑动窗口维持最大值或者最小值的更新结构，在【必备】课程【单调队列】视频里讲述 ​

长度最小的子数组 ​

题目链接 ​

https://leetcode.cn/problems/minimum-size-subarray-sum/ ​

思路分析 ​

r 不断加加，如果发现 sum - num [ i ] >= target，则尝试移动 l 使得窗口缩小，不断更新答案，得到最小的窗口长度 ​

时间复杂度：O（n），两个指针都往后移动，不回退 ​

空间复杂度：O（1），只用了有限级变量 ​

代码实现 ​

java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        for (int l = 0, r = 0, sum = 0; r < nums.length; r++) {
            sum += nums[r];
            // 如果发现 sum - num[l] >= target 就尝试缩小窗口
            while (sum - nums[l] >= target) {
                sum -= nums[l++];
            }
            // 如果满足条件，不断更新最小窗口长度
            if (sum >= target) {
                ans = Math.min(ans, r - l + 1);
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

无重复字符的最长字串 ​

题目链接 ​

https://leetcode.cn/problems/longest-substring-without-repeating-characters/ ​

思路分析 ​

考虑到都是字母，可以用 ASCLL 码值作为下标与数组的映射关系，记录每个字符是否出现过 ​

如果 l++ 发现该位置的字符在之前的窗口出现过，则更新 l 为 Math.max（l，该字符上一次出现的位置 + 1），大的会离当前窗口的右边界更近 ​

情况一：d c e f z k e，此时 l 指向 d，r 指向 z，当 r++ 发现 e 之前出现过，l 更新到 e 上一次出现的位置 + 1 的位置，即 f 位置 ​

情况二：f.....abcde f，此时 l 指向 a，r 指向 e，当 l++，发现 f 在窗口的前面，应该更新左窗口为 l 位置，由于 l 是因为出现了重复字符才移动的，因此 a 往左可能会和当前窗口中的某个字符重复，l 要保留在当前的 a 位置，即取Math.max（l，该字符上一次出现的位置 + 1） ​

代码实现 ​

java
class Solution {
    // 原来这里是 s，这里改成 str
    public int lengthOfLongestSubstring(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        // 无符号 char 类型的字符都在 0 - 255 范围内
        // 用数组下标的映射关系表示每一种字符上次出现的位置
        int[] last = new int[256];
        // 初始都填 -1，不会影响计算的结果
        Arrays.fill(last, -1);
        // 不含有重复字串的最长字串的长度
        int ans = 0;
        for (int l = 0, r = 0; r < n; r++) {
            // 只有发现当前字符出现过才更新 l
            // 如果没有出现过，数组默认值为 -1
            // +1 后为 0，不影响 l 的位置
            l = Math.max(l, last[s[r]] + 1);
            ans = Math.max(ans, r - l + 1);
            // 更新当前字符上一次出现的位置
            last[s[r]] = r;
        }
        return ans;
    }
}

最小覆盖字串 ​

题目链接 ​

https://leetcode.cn/problems/minimum-window-substring/ ​

思路分析 ​

本题采用负债表模型，记录每一个字符的欠债情况，总债务为目标字符串的长度 ​

r++ 往右移动，当发现总债务还清时，开始移动 l，尝试缩小窗口，这个过程中需要保证原先的还的债务不能再欠回来，如果债务大于 0，说明这是无效的还债，不影响最终的结果 ​

代码实现 ​

java
class Solution {
    // 原来是 String s, String t，这里改成 String str, String tar
    public String minWindow(String str, String tar) {
        char[] s = str.toCharArray();
        char[] t = tar.toCharArray();
        // cnts 数组记录每个字符的欠债情况
        // cnts[i] = 负数，代表字符 i 有欠债
        // cnts[i] = 正数，代表字符 i 有盈余
        int[] cnts = new int[256];
        for (char cha : t) {
            cnts[cha]--;
        }
        // 最小覆盖字串的长度
        int len = Integer.MAX_VALUE;
        // 从哪个位置开头发现的最小覆盖字串
        int start = 0;
        // 总债务
        int debt = t.length;
        for (int l = 0, r = 0; r < s.length; r++) {
            // 窗口右边界向右，给出字符还债
            if (cnts[s[r]] < 0) {
                debt--;
            }
            // 无论是还债还是盈余，r 向右移动，cnts[s[r]] 都要加加
            // 表示该字符出现过，记录出现次数
            cnts[s[r]]++;
            // 债务还清，尝试缩小窗口长度，移动 l
            if (debt == 0) {
                // 只要字符不再次欠债，持续减少盈余部分
                while (cnts[s[l]] > 0) {
                    cnts[s[l]]--;
                    l++;
                }
                // 发现了更小的窗口长度，更新答案，记录起始位置
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    start = l;
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : str.substring(start, start + len);
    }
}

加油站 ​

题目链接 ​

https://leetcode.cn/problems/gas-station/ ​

思路分析 ​

计算对应位置的差值，即 gas [ i ] - cost [ i ]，记为剩余油量数组，表示从 i 位置到 i+1 位置的剩余油量，如果为负数，则说明从 i 出发无法到达 i + 1 位置 ​

本题要求的是走一圈，转圜的过程可以使用 % 运算实现 ​

题目转化为给定一个子数组（剩余油量），尝试每个起点，走一圈看累加和是否大于 0，如果符合条件，返回出发时加油站的编号 ​

窗口左边界的移动逻辑：[ l，r - 1 ] 窗口的累加和大于 0，当 r 进来时，发现累加和小于 0，此时认为从 l 到 r 范围内的任何一个数作为起点都无法转一圈（即累加和小于 0），则下一轮窗口的左边界 l 来到 r + 1 位置即可 ​

因为在 [ l，r -1 ] 这么多数的加持下，加入 r 都会导致累加和小于 0，那 l 到 r - 1 任何一个数，少了更多书数的支持，加入 r 后只会导致累加和更小，所以 l 到 r 范围内的任何一个数作为起点都无法转一圈 ​

代码实现 ​

java
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        // 定义串口的范围是 [l,r) 左闭右开，r 位置到不了
        // 如果发现累加和小于 0，则下一轮 l 来到 r + 1 位置
        for (int l = 0, r = 0, sum; l < n; l = r + 1, r = l) {
            // 每一轮循环清空累加和
            sum = 0;
            while (sum + (gas[r % n] - cost[r % n]) >= 0) {
                // 窗口转了一圈，且累加和大于0，返回起始位置
                if (r - l + 1 == n) {
                    return l;
                }
                // r 位置进来
                sum += gas[r % n] - cost[r % n];
                // r 来到 r + 1 位置，[l, r + 1]
                r++;
            }
        }
        return -1;
    }
}

替换字串得到平衡字串 ​

题目链接 ​

https://leetcode.cn/problems/replace-the-substring-for-balanced-string/ ​

思路分析 ​

统计每个字符的词频，如果大于 n ，说明需要拿出多余的部分来替换，将不够 n / 4 的字符个数补齐 ​

本题类似欠债模型，即转化为最小覆盖字串问题。大于 n / 4 部分的字符个数认为是欠债，找到某个区间包含这些欠债的字符，那这些字符一定可以替换为其他字符去补齐不够 n / 4 的字符个数，使得最后的字串平衡 ​

代码实现 ​

java
class Solution {
    // 原来这里是 String s，这里改成 str
    public int balancedString(String str) {
        int n = str.length();
        int[] s = new int[n];
        // 只有 Q W E R 四种字符
        int[] cnts = new int[4];
        // 统计词频
        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);
            // 将字符转化为如下形式，每个字符对一个数字
            // Q   0
            // W   1
            // E   2
            // R   3
            // 使其可以与 cnts 的下标对应，方便统计词频
            s[i] = c == 'W' ? 1 : (c == 'E' ? 2 : (c == 'R' ? 3 : 0));
            cnts[s[i]]++;
        }
        int debt = 0;
        for (int i = 0; i < 4; i++) {
            // 不够 n / 4，是要补的，认为不欠债
            if (cnts[i] < n / 4) {
                cnts[i] = 0;
            } else {
                // 这部分就是多的，需要替换成其他字符去补齐不够 n / 4 的字符
                // 小的 - 大的，得到负数
                cnts[i] = n / 4 - cnts[i];
                // 减去一个负数，得到正数
                debt -= cnts[i];
            }
        }

        // 是平衡字符串，返回 0
        if (debt == 0) {
            return 0;
        }

        // 最小覆盖字串的逻辑
        int ans = Integer.MAX_VALUE;
        for (int l = 0, r = 0; r < n; r++) {
            if (cnts[s[r]] < 0) {
                debt--;
            }
            cnts[s[r]]++;
            if (debt == 0) {
                while (cnts[s[l]] > 0) {
                    cnts[s[l]]--;
                    l++;
                }
                ans = Math.min(ans, r - l + 1);
            }
        }
        return ans;
    }
}

K 个不同整数的子数组 ​

题目链接 ​

https://leetcode.cn/problems/subarrays-with-k-different-integers/ ​

思路分析 ​

本题转化：（=k 的不同子数组个数） = （<= k 的子数组个数） - （<= k - 1 的子数组个数） ​

即转为求 <= k 种不同数的子数组个数，本题关注的是不同子数组的个数，而不是所有的子数组的个数，例如数组 [ 1, 2, 3, 4 ]，0 - 3 位置，1 - 3 位置，2 - 3 位置，3 - 3 位置，一共四个 ​

只需要统计词频，表示字符的种类数，每个窗口中有多少种不同整数的子数组可以用 r - l + 1 计算，如果发现种类数 > k 了，l 往右移动，缩小窗口 ​

代码实现 ​

java
class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        // （=k 的不同子数组个数） = （<= k 的子数组个数） - （<= k - 1 的子数组个数）
        return numsOfMostKinds(nums, k) - numsOfMostKinds(nums, k - 1);
    }

    public int MAXN = 20001;

    // 返回 <= k 的不同子数组个数
    public int numsOfMostKinds(int[] arr, int k) {
        // 不同种类的子数组个数
        int ans = 0;
        // 避免多组测试用例带来的脏数据影响，每次调用重新创建新数组
        int[] cnts = new int[MAXN];
        for (int l = 0, r = 0, collect = 0; r < arr.length; r++) {
            // r 位置的词频加一发现等于 1，说明之前没有出现过，统计种类数
            if (++cnts[arr[r]] == 1) {
                collect++;
            }
            // 种类数多了，移动 l，缩小窗口
            while (collect > k) {
                // 种类数为 0，更新种类数
                if (--cnts[arr[l]] == 0) {
                    collect--;
                }
                l++;
            }
            // 例如 [1, 2, 3, 4]，不同种类数的子数组如下
            // 0 - 3 位置、1 - 3 位置、2 - 3 位置、3 - 3 位置
            ans += r - l + 1;
        }
        return ans;
    }
}

至少有 K 个重复字符的最长子串 ​

题目链接 ​

https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/ ​

思路分析 ​

本题采用滑动窗口的前提是只有 26 个字符，根据数据量猜解法 ​

本题的难点在于没有单调性，通过种类的约束实现单调性，使用 collect 表示窗口中收集到的字符的种类数，satisfy 表示窗口中字符出现次数 >=k 的种类数 ​

本题思路转化，只有 1 / 2 / 3.... / 26 种字符且出现次数 >= k 的最长字串，在其中求最大值 ​

代码实现 ​

java
class Solution {
    // 原来这里是 String s，这里改成 str
    public int longestSubstring(String str, int k) {
        char[] s = str.toCharArray();
        int n = s.length;
        // 统计词频
        int[] cnts = new int[256];
        int ans = 0;
        // 每次要求字串必须含有 require 种字符，每中字符出现的次数
        // 都必须 >= k词，求出符合条件的最长字串，在其中求最大值
        // 由于只有 26 种字符，可以使用枚举，这是使用滑动窗口的前提
        for (int require = 1; require <= 26; require++) {
            Arrays.fill(cnts, 0);
            // collect ；窗口中收集到的字符的种类数
            // satisfy ：窗口中字符出现次数 >=k 的种类数
            for (int l = 0, r = 0, collect = 0, satisfy = 0; r < n; r++) {
                cnts[s[r]]++;
                if (cnts[s[r]] == 1) {
                    collect++;
                }
                if (cnts[s[r]] == k) {
                    satisfy++;
                }
                // 种类数出了本轮的限制，移动 l，缩小窗口
                while (collect > require) {
                    // 在 cnt[s[l]]-- 之前判断
                    if (cnts[s[l]] == 1) {
                        collect--;
                    }
                    if (cnts[s[l]] == k) {
                        satisfy--;
                    }
                    cnts[s[l]]--;
                    l++;
                }
                // 此时表示字串以 r 位置结尾，且种类数不超的最大长度
                if (satisfy == require) {
                    ans = Math.max(ans, r - l + 1);
                }
            }
        }
        return ans;
    }
}

Copyright © 2025 Jackson 凌 All Rights Reserved. | 粤ICP备2025441629号-1