← 返回学习路线

SYSTEM

滑动窗口三大变式完整考点笔记(Java)

算法
src/content/notes/algorithm/滑动窗口.md

和二分笔记格式对齐:前置总览 → 分变式(题目极简说明、题型特征、核心思路、完整模板、一句话总结)→ 速查表 → 踩坑汇总

前置总览:滑动窗口通用基础

适用场景:求连续子数组 / 连续子串问题,left、right只会向右移动,每个元素最多进、出窗口一次,时间复杂度 O(n)。

三大分类:

  1. 可变窗口‑求最小窗口:满足条件,不断收缩找最短(LC209、LC76)

  2. 可变窗口‑求最大窗口:不满足条件才收缩,合法时更新最大长度(LC1004)

  3. 固定窗口

    :窗口长度固定,维护窗口内信息,判断是否合法(LC567、LC438)

    特殊:LC30串联所有单词子串:单词级滑动窗口,移动单位不是单个字符,是完整单词。

通用伪框架

int left = 0;
for(int right = 0; right < 数组/字符串长度; right++){
    // 1. right进入窗口,更新窗口统计信息(sum、计数、哈希数组、valid)

    // 2. 判断窗口是否需要收缩(while循环收缩left)
    while(窗口不合法){
        // left移出窗口,更新统计
        left++;
    }
    // 3. 更新答案(最小窗口在while内部更新;最大/固定窗口在while结束后更新)
}

关键区分:

  • 求最短窗口:进入while(窗口合法),在while循环内部不断更新答案,压缩窗口,尽可能变小。
  • 求最长窗口:进入while(窗口不合法),while结束窗口恢复合法,循环外更新最大长度。
  • 固定窗口:窗口长度到达固定值,执行判断、更新答案,然后移出左边元素维持窗口大小。

变式一:可变窗口 · 求最小窗口(满足条件,尽量压缩窗口)

分支1:LC209 长度最小的子数组

题目极简说明:全正整数数组,找出总和 ≥ target 的最短连续子数组,无则返回0。 题型特征:数组全部正数,满足条件后,持续收缩左边界,找最小长度。 核心思路:right不断右移累加sum;sum >= target窗口合法,进入while循环,不断记录最小长度,减去左元素、left右移,直到sum不满足条件。

完整模板

public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int sum = 0;
    int res = Integer.MAX_VALUE; // 初始极大值
    for(int right = 0; right < nums.length; right++){
        sum += nums[right];
        // 窗口合法,尽可能压缩找更小窗口,【答案写在while内部】
        while(sum >= target){
            res = Math.min(res, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return res == Integer.MAX_VALUE ? 0 : res;
}

一句话总结:条件达标就收缩,while里面更新最小答案,全正数才可以用本模板。

分支2:LC76 最小覆盖子串

题目极简说明:s中找包含t全部字符(数量也要匹配)的最短子串,不存在返回空字符串。 题型特征:字符串,字符计数匹配;使用need数组记录目标字符需求;valid记录满足条件的字符种类;valid == countKind代表窗口完全合法。 核心思路:right扩张窗口,统计窗口字符;当所有字符种类满足,进入while循环,记录最小窗口,不断收缩左边界,直到窗口不再满足条件。

public String minWindow(String s, String t) {
    char[] sArr = s.toCharArray();
    int[] need = new int[128];
    int[] window = new int[128];
    int countKind = 0;
    for(char c : t.toCharArray()){
        if(need[c]==0) countKind++;
        need[c]++;
    }
    int left = 0, valid = 0;
    int start = 0, minLen = Integer.MAX_VALUE;
    for(int right = 0; right < sArr.length; right++){
        char c = sArr[right];
        if(need[c]>0){
            window[c]++;
            if(window[c]==need[c]) valid++;
        }
        // 全部种类匹配,窗口合法,收缩左边界
        while(valid == countKind){
            if(right-left+1 < minLen){
                minLen = right-left+1;
                start = left;
            }
            char lc = sArr[left];
            if(need[lc]>0){
                if(window[lc]==need[lc]) valid--;
                window[lc]--;
            }
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start+minLen);
}

一句话总结:字符计数匹配,valid等于目标种类数代表窗口合法;while循环内部更新最短子串。


变式二:可变窗口 · 求最大窗口(窗口非法才收缩,循环结束更新答案)

LC1004 最大连续1的个数III

题目极简说明:数组由0、1组成,最多把k个0翻转为1,求最长连续子数组。 题型特征:找最长合法窗口;当窗口内0的数量>k →窗口非法,才收缩left。答案写在while循环外面。 核心思路:right向右,统计窗口中0的个数;0的数量超过k,进入while收缩左边界;while结束窗口恢复合法,更新最大窗口长度。

完整模板

public int longestOnes(int[] nums, int k) {
    int left = 0;
    int zeroCount = 0;
    int maxLen = 0;
    for(int right = 0; right < nums.length; right++){
        if(nums[right]==0) zeroCount++;
        // 窗口非法才收缩
        while(zeroCount > k){
            if(nums[left]==0) zeroCount--;
            left++;
        }
        // while结束窗口一定合法,更新最大长度
        maxLen = Math.max(maxLen, right-left+1);
    }
    return maxLen;
}

一句话总结:非法才收缩,while外面更新最大窗口。


变式三:固定大小窗口(窗口长度固定不变)

代表题 LC567字符串的排列、LC438找到字符串中所有字母异位词 题目极简说明 LC567:判断s2是否存在一个子串,是s1的字母异位词(字符种类、数量完全相同)。 题型特征:合法子串长度固定等于目标字符串长度;窗口超过固定长度,就移出最左边字符维持窗口大小;窗口长度等于目标长度时判断是否匹配。 核心思路:need统计目标字符;right向右;一旦窗口长度超过目标长度,移出左字符,left++;窗口刚好等于目标长度,判断字符计数是否全部匹配。

完整模板(LC567)

public boolean checkInclusion(String s1, String s2) {
    int len1 = s1.length(), len2 = s2.length();
    if(len1>len2) return false;
    int[] need = new int[26];
    int[] window = new int[26];
    for(char c : s1.toCharArray()) need[c-'a']++;
    int left = 0;
    for(int right = 0; right < len2; right++){
        window[s2.charAt(right)-'a']++;
        // 窗口超过固定大小,收缩左边
        if(right-left+1 > len1){
            window[s2.charAt(left)-'a']--;
            left++;
        }
        // 窗口刚好等于固定长度,判断是否匹配
        if(right-left+1 == len1){
            if(check(need, window)) return true;
        }
    }
    return false;
}
private boolean check(int[] a, int[] b){
    for(int i=0;i<26;i++){
        if(a[i]!=b[i]) return false;
    }
    return true;
}

一句话总结:窗口长度卡死固定值;长度超标就移出左边元素;到达固定长度做匹配判断。

LC438和本题几乎完全一样,区别:找到匹配不return true,而是把left加入结果List,遍历结束返回集合。

特殊拓展:LC30串联所有单词的子串(单词级固定窗口)

题目极简说明:s找子串,刚好由words数组所有单词拼接而成,单词长度全部相同。 题型特征:滑动单位不是单个字符,是完整单词;用HashMap统计词频;起始偏移只需要遍历0 ~ wordLen‑1。 核心思路:need存目标单词词频;每次right += wordLen,截取单词;不在need直接重置窗口;词频超标就不断移除左边单词;匹配成功记录left下标。

一句话总结:按单词粒度滑动窗口,HashMap统计单词频次。


滑动窗口四大题型速查表(做题秒判断)

题型 代表题目 核心操作 标志性特点 更新答案位置
可变‑最小窗口 209、76 窗口合法就持续收缩,尽量压小 求最短子数组/子串 while循环内部
可变‑最大窗口 1004 窗口非法才收缩;合法保留窗口 求最长子数组 while循环外部
固定大小窗口 567、438 维持窗口长度不变,长度超标移除左边 子串长度固定等于目标长度 窗口达到固定长度时判断
单词级滑动窗口 30 以完整单词为滑动单位,HashMap词频统计 单词长度统一,匹配一组单词 匹配成功记录起点

滑动窗口高频踩坑汇总

  1. 最小窗口答案写while内部;最大窗口写while外面,千万不要写反。
  2. 数组存在负数时,普通滑动窗口会失效(单调性被破坏),需要前缀和+二分。
  3. 初始最值变量:求最小窗口设置Integer.MAX_VALUE;循环结束必须校验是否被更新过。
  4. 字符类题目:小写字母使用int[26];ASCII全部字符用int[128],性能优于HashMap。
  5. valid变量含义:满足数量要求的字符种类数,不是字符总个数。
  6. 固定窗口:right-left+1 > k的时候收缩;等于k的时候执行匹配判断。
  7. 子数组必须连续;子序列不连续,不能用滑动窗口。

对比二分笔记记忆:二分是不断压缩区间[left,right];滑动窗口left、right单向向右移动维护窗口区间。