labuladong算法笔记｜滑动窗口算法

灵神｜【题单】滑动窗口与双指针（定长/不定长/至多/至少/恰好/单序列/双序列/三指针）

今天重新整理滑动窗口的题目，开始参考灵神分享的题单并结合推荐的插件来做题。

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）

基础

1456. 定长子串中元音的最大数目 （20241218）

太强了，一看题解就懂的那种。

这个题目涉及的是定长的窗口，先往里面填充数据，在更新答案，然后在将数据剔除。

class Solution {
    public int maxVowels(String S, int k) {
        // 进入窗口、更新答案、离开窗口
        char[] s = S.toCharArray();
        int ans = 0;
        int vowel = 0;
        for(int i= 0;i<s.length;i++){
            // 进入窗口
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u'){
                vowel++;
            }
            if(i < k-1){ // i < k-1的时候就一直往里面添加
                continue;
            }
            // 更新答案
            ans = Math.max(ans, vowel);
            // 离开窗口
            char o = s[i-k+1];  // 这里i-k+1就是窗口第一个数据的下标
            if(o == 'a' || o == 'e' || o == 'i' || o == 'o' || o == 'u'){
                vowel--;
            }
        }
        return ans;
    }
}

这里我看下为什么i-k+1表示的是窗口的第一个数据的下标？

因为使用了一个位置来进行数据交换，中间是有两个数据是确定的，就是 k-1个数据是确定的，那么窗口的第一数据的下标就是 i - (k-1) ，转化就是 i - k + 1就表示窗口里面第一个数据的下标。

643. 子数组最大平均数 I（20241218）

使用模版求解。

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double ans = Integer.MIN_VALUE; // 因为求的是最大的平均值，这里要定义最小，不能定义成0.0
        double sum = 0.0;
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
            if(i < k-1){
                continue;
            }   
            ans = Math.max(ans, sum/ k);
            sum -= nums[i-k+1];
        }
        return ans;
    }
}

1343. 大小为 K 且平均值大于等于阈值的子数组数目（20241218）

使用模版求解。

2090. 半径为 k 的子数组平均值（20241219）

这个题目还是有些是值得注意的。

题目给出的窗口是以i为中心，k为半径的窗口， 里面有一些细节，像是窗口的长度len 等于2 * k + 1， 循环的时候还是循环[0, nums.length)，

对应的存放数据的下标是i-k，最前面需要移除元素的下标是i-len+1，相当于i - 2*k。

Arrays.fill(ans, -1);将所有的元素都赋值成为-1.

class Solution {
    public int[] getAverages(int[] nums, int k) {
        
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);
   
        int sum = 0;
        int len = 2 * k + 1;
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
            if(i < len - 1){  // 这里就控制了下标小于len-1的值不会向下流转
                continue;
            }  
            ans[i-k] = (int)(sum / len);  // 这里就控制了下标最多就是i-k
            sum -= nums[(int)(i-len+1)]; // 是减去最前面的下标的值
        }
        return ans;
        
    }
}

2379. 得到 K 个黑块的最少涂色次数（20241219）

标准的模版解法，只是其中转化了一下思路，求窗口里面最多的黑色块x，最后用窗口的长度减去最多的黑色块x得到答案。

在移除时候的下标是 i - (k-1) ，也就是 i-k=1；

1461. 检查一个字符串是否包含所有长度为 K 的二进制子串（20241219）

子串：连续的字符组成的字符串，一个长度为n的字符串所拥有的子串个数为： n * (n-1)/ 2 + 1，（子串是连续的）

子序列：在原来的序列中找出一部分元素组成的序列（子序列是不连续的）

长度为k的只包含字符'0'和字符'1'的子串个数等于2^k。

开始想的是把所有长度为k的为包含0和1字符的子串都求出来，然后在求出来s的所有子串进行对比。

但是可以对比这两个子串的个数来求解这一道题，肯定是 2^k >= sub(s)， 当两者想等的时候条件成立，如果2^k > sub(s)那么必定有一个或者多个子串不在s的子串里面，返回false。

class Solution {
    public boolean hasAllCodes(String S, int k) {
        // 只需要计算长度为k的由1或者0组成的串有多少个 2的k次方
        // 然后找出来s中长度为k的所有子串的个数
        StringBuilder s = new StringBuilder();
        Set<String> set = new HashSet<>();

        char[] chars = S.toCharArray();
        for(int i = 0;i<chars.length;i++){
            s.append(chars[i]);
            if(i < k-1){
                continue;
            }   
            set.add(s.toString());
            
            s.deleteCharAt(0);
        }
        return set.size() == Math.pow(2, k);
    }
}

2841. 几乎唯一子数组的最大和（20241219）

读题就读了半天， 简单来理解有两个条件， 一个是窗口里面的值求和为最大值，二个是窗口里面互不相同的元素的个数要大于等于m。

开始使用Set来做的，但是有一个用例nums = [1,1,1,3], k = 2, m=2 这个过不了，因为到[1, 3] 的时候，前面的1给从集合里面剔除掉了，导致出现了错误。

后面换成Map来做，统计每个元素的个数。

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        long sum = 0;
        long ans = 0;

        for(int i = 0;i<k-1;i++){  // 先统计前面k-1个元素的总和，并添加到map里面
            sum += nums.get(i);
            cnt.merge(nums.get(i), 1, Integer::sum);
        }

        for(int i = k-1;i<nums.size();i++){
            sum += nums.get(i);
            cnt.merge(nums.get(i), 1, Integer::sum);  // 把第k个元素放进去

            if(cnt.size() >= m){  // 判断是否满足第二个条件
                ans = Math.max(ans, sum);
            }

            sum -= nums.get(i-k+1);  // 删除元素操作
            if(cnt.merge(nums.get(i-k+1), -1, Integer::sum) == 0){  // 如果cnt减完之后value等于0的话就把他从map里面删除掉
                cnt.remove(nums.get(i-k+1));
            }
        }
        return ans;
    }
}

2461. 长度为 K 子数组中的最大和（20241219）

子数组 是数组中一段连续非空的元素序列。

子序列 是数组中非连续非空元素的序列。

这个题目和上面一个题目类似，都是在统计窗口元素和的同时，维护窗口中元素出现的次数问。

1423. 可获得的最大点数（20241219）

这个题很容易就会想到用双指针的思路来解，但是有会面临一个问题，就是左边的值和右边的值一样的情况下要怎么处理，所以换个思路思考：

拿走k张牌之后，剩下n-k张牌，这里的n是cardPoints的长度，那么剩下来的牌必然是连续的，想要求拿走的牌的最大点数，其实可以逆向思维思考，求剩下的连续的最小和，所以题目就变成了： 求窗口长度为n-k的最小和，然后用总和见到最小和就是题目所求的。

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        
        k = cardPoints.length - k;
        
        long sum = 0;
        long ans = Integer.MAX_VALUE;
        long total = 0;
        for(int i = 0;i<cardPoints.length;i++){
            total += cardPoints[i];
        }
        if(k == 0){
            return (int)total;
        }

        for(int i = 0;i<cardPoints.length;i++){
            sum += cardPoints[i];
            
            if(i < k-1){
                continue;
            }
            ans = Math.min(ans, sum);
            sum -= cardPoints[i-k+1];
        }
        return (int)(total - ans);
        
    }
}

1652. 拆炸弹（20241220）

我悟到了

仔细阅读题目之后，我们都明白了，当k=0时全为1；当k>0的时候，值等于当前下标后面k个元素的和；当k<0时，值等于当前下标前面k个元素的和。

可以看出来，定长窗口都是向右移动的，重要的是确定第一个窗口的位置在哪里， 窗口的长度都是k。

当k>0的时候，我们很容易得到第一个窗口是 [1, k+1)（左端点为参照），当k<0时，我们也能够得到窗口的下标 [n - |k|, n)（右端点为参照）。

还需要解决的一个问题就是添加元素的下标和剔除元素的下标？

我们统一第一个窗口右侧下标为r， 那么窗口左侧下标就是r-|k|， 然后求余数分别就是[r%n, (r-|k|) % n]。

class Solution {
    public int[] decrypt(int[] code, int k) {
        int n = code.length;
        int[] ans = new int[n];

        // r表示第一个窗口的右边下标
        // 所以构建出来一个长度为k，窗口下标为[r-1, r]的窗口
        int r = k> 0? k+1: n;  
        
        k = Math.abs(k);
        int s = 0;

        for(int i = r-k;i<r;i++){
            s += code[i];  // 计算ans[0]
        }
        for(int i = 0;i<n;i++){ 
            ans[i] = s;
            s += code[r % n] - code[(r-k) %n];
            r++;  // 每次i向后移动一位，r也向后移动一位
        }
        return ans;
        
    }
}

1297. 子串的最大出现次数（20241220）

满足两个条件：1 子串不同字符个数小于maxLetters；2 子串长度大于minSize，小于maxSize

要出现次数最多，那么子串的长度就尽量短，所以可以转化成固定窗口长度为minSize的滑动窗口题目

结合灵神定长滑动窗口的思路解题。

补充：求map最大的value -> map.values().stream().max(Integer::compareTo).orElse(0);

class Solution {
    public static int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        // 满足两个条件：1 不同字符个数小于maxLetters；2 子串长度大于minsize，小于maxsize
        // 要出现次数最多，那么子串的长度就尽量短，所以可以转化成固定窗口长度为minSize的滑动窗口题目

        // 用来统计子串中不同字符的个数
        Map<Character, Integer> cnt = new HashMap<>();
        // 用来记录满足条件的子串出现的次数
        Map<String, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        // 子串
        StringBuilder str = new StringBuilder();
        for(int i = 0;i<chars.length;i++){
            // in
            cnt.merge(chars[i], 1, Integer::sum);
            str.append(chars[i]);
            if(i< minSize - 1){
                continue;
            }
            //
            if(cnt.size() <= maxLetters){
                map.merge(str.toString(), 1, Integer::sum);
            }
            // out
            str.deleteCharAt(0);

            if(cnt.merge(chars[i-minSize+1], -1, Integer::sum) == 0){
                cnt.remove(chars[i-minSize+1]);
            }
        }
        return map.values().stream().max(Integer::compareTo).orElse(0);
    }
}

2653. 滑动子数组的美丽值（20241220）

计数排序： ...

class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        // 计数排序
        final int BIAS = 50;
        int[] cnt = new int[2 * BIAS + 1];  // 因为有101个数，[-50, 50], 这里在存的时候有50的偏移量。
        for(int i =0;i<k-1;i++){ // 先往窗口里面添加k-1个数
            cnt[nums[i] + BIAS]++;
        }
        int n = nums.length;
        int[] ans = new int[n-k+1];
        
        for(int i=k-1;i<n;i++){
            cnt[nums[i] + BIAS]++;
            int left = x;
            for(int j =0;j<BIAS;j++){
                left -= cnt[j];
                if(left<=0){
                    ans[i-k+1] = j-BIAS;
                    break;
                }
            }
            cnt[nums[i-k+1] + BIAS]--;
        }
        return ans;
    }
}

二、不定长滑动窗口

不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，以及求子数组的个数。

2.1、求最长或最大

3. 无重复字符的最长子串（20241223）

主要的思路就是把右侧的数据添加进来，然后判断是否已经存在了，如果已经存在了，那就缩小左边的窗口，直到没有重复的元素；如果不存在，就将元素添加到窗口里面。

class Solution {
    public int lengthOfLongestSubstring(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int ans = 0;
        int left = 0;  // 窗口左端点
        boolean[] has = new boolean[128];       
        for(int right=0;right<n;right++){
            // 窗口右端点添加一个字符，判断是不是已经存在了
            while(has[s[right]]){ // 如果存在了，就缩小窗口
                has[s[left]] = false;
                left++;  // 缩小窗口
            }
            has[s[right]] = true;  // 否则就更新
            ans = Math.max(ans, right - left + 1);  // 然后更新答案
        }
        return ans;
    }
}

3090. 每个字符最多出现两次的最长子字符串（20241223）

字符不重复解题思路相同， 只需要改变判断次数的代码。

有一个可以优化的思路，就是之前是用的Map<Character, Integer> has = new HashMap<>();来判断出现次数的；可以直接用数组来判断int[] has = new int[26];因为只有26个小写的英文字符。

class Solution {
    public int maximumLengthSubstring(String S) {
        char[] s = S.toCharArray();
        int ans = 0;
        int left = 0;

        int[] cnt = new int[26]; // 26个字母，用数组来保存26个小写字符

        for(int i=0;i<s.length;i++){
            int b = s[i] - 'a';
            cnt[b]++;
            while(cnt[b] > 2){
                cnt[s[left] - 'a']--;
                left++;
            }
            ans = Math.max(ans, i - left + 1);
        }
        return ans;       
    }
}

1493. 删掉一个元素以后全为 1 的最长子数组（20241223）

因为求删除一个元素后全为1的最长子数组，求包含一个0，其他全为1的最长子数组。

当nums全为1的时候也同样满足。

class Solution {
    public int longestSubarray(int[] nums) {
        // 求包含一个0的最长子串
        int ans= 0 ;
        int cnt = 0;
        int left = 0;

        for(int right = 0;right<nums.length;right++){
            // 先添加
            if(nums[right] == 0){
                cnt++;
            }
            // 判断条件
            while(cnt > 1){
                if(nums[left] == 0){
                    cnt--;
                }
                left++;  // 把left++放到这里是因为，如果是1的时候cnt不做处理，直接跳过
            }
            // 更新答案
            ans = Math.max(ans, right-left+1);
        }
        return ans-1;
    }
}

1208. 尽可能使字符串相等（20241224）

对于这个题目，我甚至连题目都没有看懂，但是在看到下面题解关于题目的讲解的时候，我就明白了。

在看到costs数组等于[1,1,1,2]的时候，在结合maxCost = 3的时候，解题思路就明朗了，就是先将两个字符穿转化的开销维护起来， 在使用灵神不定长滑动窗口的解题模板，很快就能解决了。

看来理解题目对于解题是相当重要的。

2730. 找到最长的半重复子字符串（20241224）

这个题题目理解起来还是比较容易的，就是求最多只有一对相邻字符的最大的子串。

定义same表示相同字符的对数，移动right， 当same>1的时候，就移动left，直到left和left-1对应的值相同，然后把same置为1。

这里容易陷入一个误区，就是可能会统计每个字符出现的次数，因为相同字符的对数不一样的话，处理的逻辑也不一样。

class Solution {
    public int longestSemiRepetitiveSubstring(String S) {
        char[] s = S.toCharArray();
        int same = 0;  // 记录相同字符对数出现的次数
        int ans =1;
        int left = 0;
        
        for(int right = 1;right<s.length;right++){
            if(s[right] == s[right-1]){
                same++;
            }
            if(same > 1){
                left++;
                while(s[left] != s[left-1]){
                    left++;
                }
                same = 1;
            }
            ans = Math.max(ans, right-left+1);
        }
        return ans;
    }
}

904. 水果成篮（20241225）

喵的题解都看不懂的题

用哈希表来处理要好容易理解一点。

class Solution {
    public static int totalFruit(int[] fruits) {
        int ans = 0;
        int left = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int right=0;right<fruits.length;right++){
            // 添加数据到cnt里面
            cnt.merge(fruits[right], 1, Integer::sum);

            while(cnt.size() > 2){
                // 当size大于2的时候，就把左指针的数据remove掉
                cnt.merge(fruits[left], -1, Integer::sum);
                if(cnt.get(fruits[left]) == 0){
                    cnt.remove(fruits[left]);
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

还需要理解一个就是， ++i和i++的区别。

public class Q904 {
    public void test2(){
        int a = 1;
        int b = 1;
        int c = 1;
        int d = 1;
      
      	// ++a 表示先运算a = a+1， 在执行a+1 == 1
        System.out.println(++a == 1);
      	// b++ 表示先运算 b == 1，然后在执行b = b+1
        System.out.println(b++ == 1);
        // true
        System.out.println(1 == c++);
        // false
        System.out.println(1 == ++d);
    }
}

1695. 删除子数组的最大得分（20241226）

题目的意思就是：求最大元素只出现一次的子数组的和。不定长滑动窗口求解。

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        // 求所有元素只出现一次的最大数组和
        int sum = 0;
        int left = 0;
        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int right = 0;right<nums.length;right++){
            // 添加
            cnt.merge(nums[right], 1, Integer::sum);
            sum += nums[right];
            
            while(cnt.get(nums[right]) >= 2){
                if(cnt.merge(nums[left], -1, Integer::sum) == 0){
                    cnt.remove(nums[left]);
                }
                sum -= nums[left];
                left++;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

2958. 最多 K 个重复元素的最长子数组（20241226）

和上面一题是相同的解决思路，相同的代码这里就不贴了。

刚才考虑到一个问题，就是用map能解决，用int[]数组能解决吗？

用数组可能不行，因为你不知道创建的数组的长度是多少， 给出的1 <= nums[i] <= 10^9, 1 <= nums.length <= 10^5 ，如果创建一个10^5大的数组，那么空间复杂度就非常的高。

2024. 考试的最大困扰度（20241227）

说实话，这个题我是看懂了的，但是就是写不出来。灵神的位运算现在的我还看不懂，后面学到的时候在回过头来看。

题意：求answerKey的一个最长子串，至多包含k个T或者至多包含k个F

滑动窗口

public class Q2024 {
    public static int maxConsecutiveAnswers(String answerKey, int k) {
        char[] s = answerKey.toCharArray();
        int ans = 0;
        int left = 0;
        // 统计T和F的个数
        int[] cnt = new int[2];
        for (int right = 0; right < s.length; right++) {
            // 存入到cnt里面
            cnt[s[right] >> 1 & 1]++;
            // 如果T的个数或者F的个数大于k，这里就是重要的判断
            while (cnt[0] > k && cnt[1] > k) {
                // 就把left位置所在的符号的次数减一
                cnt[s[left++] >> 1 & 1]--;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

1004. 最大连续1的个数 III（20241227）

这个和上面一样的解题思路，确定不满足题意的条件，就是当子数组里面0出现的次数大于k的时候，就需要移动左端窗口了。

解题代码类似：

class Solution {
    public int longestOnes(int[] nums, int k) {
        // nums包含的0不超过k的最长子数组
        int ans = 0;
        int left = 0;
        int[] cnt = new int[2];
        for(int right=0; right<nums.length;right++){
            cnt[nums[right]]++;
            while(cnt[0] > k){
                cnt[nums[left++]]--;
            }
            ans = Math.max(ans, right- left+1);
        }
        return ans;       
    }
}

1658. 将 x 减到 0 的最小操作数（20241227）

逆向思维解这道题，x恰好减到0的最小操作数，可以想成求和为s-x的最长子数组，s表示数组的和。

class Solution {
    public int minOperations(int[] nums, int x) {        
        // 求和， 使用Arrays.stream(nums).sum()的效率很慢
        int sum = 0 ;

        for(int n: nums){
            sum += n;
        }
        // 如果全部删除也不能为0就直接返回-1
        if(sum - x < 0){
            return -1;
        }
        // 当大于的时候就添加
        int ans = -1;
        int left = 0;
        int total = 0;

        for(int right = 0;right<nums.length;right++){
            total += nums[right];
            while(total > sum-x){
                total -= nums[left++];
            }
            if(total == sum - x){
                ans = Math.max(ans, right - left + 1);
            }
        }
        return ans == -1? -1: nums.length - ans;
    }
}

Changelog

Last Updated: View All Changelog

• 3d2e0-

  feat(wiki): algo: 算法总结

  On 3/30/25