算法训练-6高效算法部分 滑动窗口

前言

滑动窗口主要解决“满足某个条件的连续子串”问题，因为我们枚举 区间、子数组、子串 问题的时候时间复杂度是$O(n^2)$，使用滑窗可以将时间复杂度优化至$O(n)$。

代码模板如下：

for (int l = 0, r = 0 ; r < n ; r++) {
    // 如果右指针的元素加入到窗口内后，根据题目判断进行滑动左指针
    while (l <= r && check()) l++;
}

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成.

题目解析

题目旨在找到最长的无重复的子串，所以我们在滑窗的过程中，只要保证窗口中元素一直是处于不重复的情况即可。换句话说，只要右指针的元素已经出现了重复，我们就滑动左指针。

代码解析

class Solution {

    // lengthOfLongestSubstring 方法用于计算给定字符串 s 中最长不重复子串的长度
    public int lengthOfLongestSubstring(String s) {
        // 创建一个大小为 128 的数组，用以存储字符出现的次数，基于 ASCII 字符集
        int[] occ = new int[128];
        // 初始化结果 res 为 0，它将用来记录最长不重复子串的长度
        int res = 0;
        // l 和 r 分别是滑动窗口的左右边界
        for (int l = 0, r = 0; r < s.length(); r++) {
            // 当 r 在 s 的长度范围内时，执行循环
            // 循环体内逻辑：如果 l 小于等于 r 并且字符 s.charAt(r) 已经出现过（occ[s.charAt(r)] 为 1），
            // 则向前移动左边界 l，直到 s.charAt(l) 没有出现过（occ[s.charAt(l)] 变为 0）
            while (l <= r && occ[s.charAt(r)] == 1) occ[s.charAt(l++)] = 0;
            // 将字符 s.charAt(r) 的出现次数置为 1，表示当前字符已经出现过
            occ[s.charAt(r)] = 1;
            // 更新结果 res 为 r - l + 1 和当前 res 之间的较大值，r - l + 1 表示当前滑动窗口的长度
            res = Math.max(res, r - l + 1);
        }
        // 返回最长不重复子串的长度
        return res;
    }
}

重复的DNA序列

DNA序列 由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。

例如，“ACGAATTCCG” 是一个 DNA序列 。 在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：
输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 输出：[“AAAAACCCCC”,“CCCCCAAAAA”] 

示例 2：
输入：s = “AAAAAAAAAAAAA” 输出：[“AAAAAAAAAA”]

提示：
0 <= s.length <= 105 s[i]==‘A’、‘C’、‘G’ or ‘T’

题目解析

此题比较简单，因为已经固定了窗口大小为10，因此我们只需要用一个指针即可，因为左指针一旦确定，右指针必然位于后10位。 因此，固定窗口的滑窗其实可以直接一层loop就可以了。

代码解析

class Solution {

    // findRepeatedDnaSequences 方法用于找出字符串 s 中所有重复出现的 DNA 序列
    public List findRepeatedDnaSequences(String s) {
        // 使用 HashSet 存储已经出现过的 DNA 子串
        Set<String> occ = new HashSet<>();
        // 使用 HashSet 存储出现次数超过一次的 DNA 子串，即重复出现的序列
        Set<String> res = new HashSet<>();
        // 遍历字符串 s，步长为 1，直到 s 的长度减去 10（因为我们要取长度为 10 的子串）
        for (int i = 0; i < s.length() - 9; i++) {
            // 取从索引 i 开始的、长度为 10 的 DNA 子串
            String sub = s.substring(i, i + 10);
            // 如果 occ 已经包含当前子串 sub，则将该子串添加到 res 中
            if (occ.contains(sub)) res.add(sub);
            // 将当前子串添加到 occ 中，以便后续检查重复
            occ.add(sub);
        }
        // 创建一个 LinkedList 用于存储最终结果
        List<String> ans = new LinkedList<>();
        // 将 res 中的所有元素添加到 ans 中
        ans.addAll(res);
        // 返回重复出现的 DNA 序列列表
        return ans;
    }
}

最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC” 

示例 2：
输入：s = “a”, t = “a” 输出：“a” 

示例 3:
输入: s = “a”, t = “aa” 输出: “” 
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：
1 <= s.length, t.length <= 105, s 和 t 由英文字母组成

题目解析

判断某个子串是否包含字符串t，只需要判断是否包含t中所有的字符（数量也要满足大于等于的关系）即可。而且题目中也说明了，只有英文字母，大写字母”A”的ASCII码是65，小写字母’z’的ASCII码是122，因此他们之间一共有58个字符，所以我们只需要开一个长度有58的数组来表示每个字符的出现次数即可。

代码解析

class Solution {
    // win 数组用于存储字符串 s 中每个字符出现的次数
    int[] win = new int[58];
    // tcnter 数组用于存储字符串 t 中每个字符出现的次数
    int[] tcnter = new int[58];

    // check 方法用于检查当前滑动窗口是否包含 t 中的所有字符
    boolean check() {
        // 遍历 tcnter 数组，如果 tcnter 数组中的任意元素大于 win 数组中对应的元素，则返回 false
        for (int i = 0; i < 58; i++) {
            if (tcnter[i] > win[i]) {
                return false;
            }
        }
        // 如果所有字符都满足条件，则返回 true
        return true;
    }

    // minWindow 方法用于找出包含字符串 t 中所有字符的最短子串
    public String minWindow(String s, String t) {
        // 遍历字符串 t，并对 t 中的每个字符进行计数
        for (char c : t.toCharArray()) {
            tcnter[c - 'A']++;
        }
        // 将字符串 s 转为字符数组
        char[] cs = s.toCharArray();
        // 初始化最短子串的长度为一个足够大的数，最短子串的起始索引为 -1
        int minlen = 100010, st = -1;
        // 初始化左右指针 l 和 r
        int l = 0, r = 0;
        // 遍历字符串 s
        for (; r < cs.length; r++) {
            // 增加字符 cs[r] 在 win 数组中的计数
            win[cs[r] - 'A']++;
            // 当滑动窗口满足条件时，尝试缩小窗口
            while (l <= r && check()) {
                // 如果当前窗口的长度小于已知最短长度，则更新最短长度和起始索引
                if (r - l + 1 < minlen) {
                    minlen = r - l + 1;
                    st = l;
                }
                // 缩小窗口，移除左侧字符，并向前移动左指针
                win[cs[l++] - 'A']--;
            }
        }
        // 如果未找到满足条件的子串，则返回空字符串；否则返回最短子串
        return st == -1 ? "" : s.substring(st, st + minlen);
    }
}

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 $[nums_l, nums_{l+1}, …, nums_{r-1}, nums_r]$ ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 
输出：2 
解释：子数组 [4,3] 是该条件下的长度最小的子数组。 

示例 2：
输入：target = 4, nums = [1,4,4] 
输出：1 

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 
输出：0

提示：
1 <= target <= 10^9, 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^5

题目解析

要求子数组的和要满足大于等于target，且要最小，因此我们只需要在当前窗口内的元素满足大于等于target的时候，我们就尝试去缩小区间，试试能够找出更小的区间。

代码解析

class Solution {

    // minSubArrayLen 方法用于找出包含目标值 target 的最短子数组的长度
    public int minSubArrayLen(int target, int[] nums) {
        // 初始化结果 res 为整数的最大值，用于记录最短长度
        int res = Integer.MAX_VALUE;
        // 初始化左右指针 l 和 r，以及滑动窗口的和 sum
        for (int l = 0, r = 0, sum = 0; r < nums.length; r++) {
            // 将右指针所指元素的值加到 sum 上
            sum += nums[r];
            // 当左指针小于等于右指针且 sum 大于等于 target 时，尝试缩小窗口
            while (l <= r && sum >= target) {
                // 更新最短长度的记录
                res = Math.min(res, r - l + 1);
                // 从滑动窗口中移除左指针所指的元素，并更新 sum，然后右移左指针
                sum -= nums[l++];
            }
        }
        // 如果 res 仍然是 Integer.MAX_VALUE，说明没有找到包含 target 的子数组，返回 0
        // 否则返回找到的最短长度
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：
输入：s1 = “ab” s2 = “eidbaooo” 
输出：true 
解释：s2 包含 s1 的排列之一 (“ba”). 

示例 2：
输入：s1= “ab” s2 = “eidboaoo” 
输出：false

提示：
1 <= s1.length, s2.length <= 10^4, s1 和 s2 仅包含小写字母

题目解析

此题依然是固定大小的滑动窗口，我们只需要用一个与s1等长的窗口进行滑动即可。

代码解析

class Solution {
    
    // s1_cnter 数组用于存储字符串 s1 中每个字符出现的次数
    int[] s1_cnter = new int[26];
    // s2_cnter 数组用于存储滑动窗口中字符串 s2 的每个字符出现的次数
    int[] s2_cnter = new int[26];

    // check 方法用于检查 s2_cnter 是否包含 s1_cnter 中的所有字符及其出现次数
    boolean check() {
        // 遍历 26 个字母，检查 s1_cnter 中的每个字符出现次数是否不小于 s2_cnter 中的相应字符出现次数
        for (int i = 0; i < 26; i++) {
            if (s1_cnter[i] < s2_cnter[i]) {
                return false; // 如果 s2_cnter 中的字符出现次数小于 s1_cnter 中的，返回 false
            }
        }
        // 如果所有字符的出现次数都满足条件，则返回 true
        return true;
    }

    // checkInclusion 方法用于检查 s1 是否可以作为 s2 的连续子序列
    public boolean checkInclusion(String s1, String s2) {
        // 如果 s1 的长度大于 s2 的长度，那么 s1 不可能是 s2 的子序列，直接返回 false
        if (s1.length() > s2.length()) {
            return false;
        }
        // 初始化 s1_cnter 和 s2_cnter 中的字符计数
        for (int i = 0; i < s1.length(); i++) {
            s1_cnter[s1.charAt(i) - 'a']++;
            s2_cnter[s2.charAt(i) - 'a']++;
        }
        // 检查初始窗口是否满足条件
        if (check()) {
            return true;
        }
        // 使用滑动窗口技术，从 s2 的第二个字符开始，向右滑动窗口，直到窗口的右端到达 s2 的末尾
        for (int l = 0, r = s1.length(); r < s2.length(); r++, l++) {
            // 将窗口右端字符的计数加一
            s2_cnter[s2.charAt(r) - 'a']++;
            // 将窗口左端字符的计数减一，实现窗口的滑动
            s2_cnter[s2.charAt(l) - 'a']--;
            // 检查当前窗口是否满足条件
            if (check()) {
                return true;
            }
        }
        // 如果所有窗口都不满足条件，则返回 false
        return false;
    }
}

尽可能使字符串相等

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

示例 1：
输入：s = “abcd”, t = “bcdf”, maxCost = 3 
输出：3 
解释：s 中的 “abc” 可以变为 “bcd”。开销为 3，所以最大长度为 3。 

示例 2：
输入：s = “abcd”, t = “cdef”, maxCost = 3 
输出：1 
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。 

示例 3：
输入：s = “abcd”, t = “acde”, maxCost = 0 
输出：1 
解释：a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。

提示：
1 <= s.length, t.length <= 10^5, 0 <= maxCost <= 10^6, s 和 t 都只含小写英文字母。

题目解析

此题的目的在于找到一个 对应位置 的子字符串，使得每个位置一一进行转换后，开销不会超过maxcost，求最长的长度。我们只需要保证窗口内的开销是小于等于maxcost即可，如果不满足则滑动左指针。

代码解析

class Solution {

    // equalSubstring 方法用于找出在给定最大成本 maxCost 的条件下，
    // 字符串 s 和 t 中相等字符的最长子串长度
    public int equalSubstring(String s, String t, int maxCost) {
        // 初始化结果 res 为 0，用于记录最长子串的长度
        int res = 0;
        // 初始化左右指针 l 和 r，以及当前窗口的总成本 sum
        for (int l = 0, r = 0, sum = 0; r < s.length(); r++) {
            // 计算当前字符对的绝对差值，并累加到 sum
            sum += Math.abs(s.charAt(r) - t.charAt(r));
            // 当左指针小于等于右指针且当前窗口的总成本大于 maxCost 时，尝试缩小窗口
            while (l <= r && sum > maxCost) {
                // 从滑动窗口中移除左指针所指的字符对的绝对差值，并更新 sum
                sum -= Math.abs(s.charAt(l) - t.charAt(l++));
            }
            // 更新结果 res 为当前窗口长度和已知最长长度中的较大值
            res = Math.max(res, r - l + 1);
        }
        // 返回最长子串的长度
        return res;
    }
}