滑动窗口算法

趙卋傑

发布于 2026-01-12 15:55:53

1410

一.长度最小的子数组

1.题目解析

长度最小的子数组

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

2.算法原理

由于此问题分析的对象是一段连续的区间，因此可以考虑使用滑动窗口的思想来解决这道题让滑动窗口满足:从位置开始，窗口内所有元素的和小于 target (那么当窗口内元素之和第一次大于等于目标值的时候，就是位置开始，满足条件的最小长度) 做法：将右端元素划入窗口中，统计出窗口内的元素和：

如果窗口内元素之和大于等于 target : 更新结果，并且将左端元素划出去的同时继续判断是否满足条件并更新结果(因为左端元素可能很小，划出去之后依旧满足条件)
如果窗口内元素之和不满足条件 : right++，另下一个元素进入窗口。

3.编写代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length,sum = 0,len = Integer.MAX_VALUE;
        //因为我们要保留最小的长度，若定义为0，则会影响结果

        for(int left = 0,right = 0;right < n;right++) {
            //1.进窗口
            sum += nums[right];
            //2.判断与目标值的大小 
            while(sum >= target){
                //3.更新结果
                len = Math.min(len,right - left + 1);
                //4.出窗口
                sum -= nums[left++];
            }
        }

        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length,sum = 0,len = Integer.MAX_VALUE;
        int left = 0,right = 0;
        //1.进窗口
        while(right < n) {
            sum += nums[right];
            //2.判断
            while(sum >= target) {
                //3.更新结果
                len = Math.min(len,right - left +1);
                //4.出窗口
                sum -= nums[left++]; 
            }
            right++;
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

二.无重复字符的最长子串

1.题目解析

无重复字符的最长字串

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

2.算法原理

暴力求解 我们要寻找的是无重复的最长子串，我们定义两个变量，我们固定一个字符后让另一个变量依次向后进行枚举即可，在往后进行枚举可以利用「哈希表」统计出字符出现的频次，来判断什么时候子串出现了重复元素。
利用规律，使用"滑动窗口"来解决问题 ①进窗口：让字符进入哈希表 ②判断：窗口内出现重复字符 ③出窗口：从哈希表中删除该字符 ④更新结果ret

3.编写代码

暴力解法

class Solution {
    public int lengthOfLongestSubstring(String ss) {
        char[] s = ss.toCharArray();
        int ret = 0,n = s.length;
        for(int left = 0;left < n;left++) {
            //定义哈希表
            int[] hash = new int[128];
            for(int right = left;right < n;right++) {
                //进哈希表
                hash[s[right]]++; 
                //出现重复元素跳出，判断下一个left
                if(hash[s[right]] > 1) {
                    break;
                }
                //没有重复就更新
                ret = Math.max(ret,right - left + 1);
            }
        }
        return ret;
    }
}

滑动窗口

//数组模拟哈希表
class Solution {
    public int lengthOfLongestSubstring(String ss) {
        char[] s = ss.toCharArray(); //将字符串强转为字符数组
        int[] hash = new int[128];
        int n = ss.length(),ret = 0;
        for(int left = 0,right = 0;right < n;right++){
            //1.进窗口
            hash[s[right]]++;//s[right]在此处为ascii码  
            //2.判断条件
            while(hash[s[right]] > 1) {
                //3.出窗口
                hash[s[left++]]--;
            }
            //4.更新结果
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }
}

//set去重
class Solution {
    public int lengthOfLongestSubstring(String ss) {
        char[] s = ss.toCharArray();
        Set<Character> set = new HashSet<>();
        int ret = 0,n = s.length;
        for(int left = 0,right = 0;right < n;right++) {
            char ch = s[right];
            //判断 出窗口  set中有重复则缩短左边界
            while(set.contains(ch)) {
                set.remove(s[left]);
                left++;
            }
            set.add(s[right]);//要将当前元素加入，因为contains判断时没有加进去且把原本的一份给删除了
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }
}

三.最大连续1的个数III

1.题目解析

最大连续1的个数III

https://leetcode.cn/problems/max-consecutive-ones-iii/description/

根据示例分析，我们可以将问题转化为找出最长的子数组，要求0的个数不超过k个

2.算法原理

暴力解法一一枚举所有的情况

滑动窗口 ①进窗口：如果是1，无视如果是0，计数器zero++ ②判断：zero>k ③出窗口：如果是1，无视如果是0，计数器zero-- ④更新结果

3.编写代码

暴力解法

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length,ret = 0;
        for(int left = 0,right = 0,zero = 0;right < n;right++) {
            if(nums[right] == 0) zero++;
            if(zero > k){
                left++;
                zero = 0;
                right = left-1;
            }
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }
}

滑动窗口

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length,ret = 0;
        for(int left = 0,right = 0,zero = 0;right < n;right++) {
            //1.进窗口
            if(nums[right] == 0) zero++;
            //2.判断
            while(zero > k) {
                //3.出窗口
                if(nums[left] == 0) zero--;
                left++;
            }
            //4.更新结果
            ret = Math.max(ret,right - left + 1);
        }
        return ret;   
    }
}

四.将x减到 0的最小操作数

1.题目解析

我们从正面思考问题，发现在操作数组时需要删除最左边或者最右边的元素，同时兼顾左右我们很难实现，那正面思考问题很难实现，我们就从反面思考问题题目要求找的是和为x的最短子串，我们将问题转换为和为sum（整个数组的和）-x的最长字串，最后用数组长度减去此问题的结果就可以得到正解

2.算法原理

进窗口： tmp += nums[right] 让right依次进窗口
判断：当tmp > target表示已经超出值
出窗口：tmp -= nums[left] 并将左侧left出窗口
更新结果：只有当 target == tmp时才更新

3.编写代码

class Solution {
    public int minOperations(int[] nums, int x) {
        int n = nums.length,sum = 0,ret = -1;  [5,6,7,8,9] x = 4 //此时直到right走到n也无法找到，所以将初值设为-1
        for(int a:nums) sum += a;
        int target = sum - x;
        if(target < 0) return -1;  //[1,1]  x = 3 此时target = 2-3<0 此时直接返回-1

        for(int left = 0,right = 0,tmp = 0;right < n;right++){
            //1.进窗口
            tmp += nums[right];
            //2.判断
            while(tmp > target) {
                //3.出窗口
                tmp -= nums[left];
                left++;
            }
            //更新  只有当相等的时候才会更新
            if(tmp == target) {
                ret = Math.max(ret,right - left + 1);
            }
        }
        if(ret == -1) return -1;
        else return n - ret;
    }
}

五.水果成蓝

1.题目解析

题目转换：找出一个最长的子数组的长度，子数组中不超过两种类型的水果

2.算法原理

在暴力枚举的基础上优化为滑动窗口算法

进窗口：将right位置元素进入到哈希表中，并记录元素的个数
判断条件：哈希表长度大于2
出窗口：将left位置的元素个数减一，当个数为0是要将该元素从哈希表中删除
更新结果

3.编写代码

容器Map实现

class Solution {
    public int totalFruit(int[] f) {
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();//统计窗口内水果种类
        int ret = 0;
        
        for(int left = 0,right = 0;right < f.length;right++) {
            int in = f[right];
            hash.put(in,hash.getOrDefault(in,0) + 1);  //进窗口
            //hash.getOrDefault(in,0)++ 哈希表中没有该元素就将该元素的value设为0，有则再原基础上++
            while(hash.size() > 2) {
                int out = f[left];
                hash.put(out,hash.get(out)-1); //出窗口
                if(hash.get(out) == 0) {
                    hash.remove(out);
                }
                left++;
            }
            //更新结果
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }
}

数组模拟哈希表实现

class Solution {
    public int totalFruit(int[] f) {
        int n = f.length;
        int[] hash = new int[n];//统计窗口内水果种类
        int ret = 0;
        
        for(int left = 0,right = 0,kinds = 0;right < n;right++) {
            int in = f[right];
            if(hash[in] == 0) {
                kinds++;
            }
            hash[in]++;  //进窗口并统计元素个数
            while(kinds > 2) {
                int out = f[left];
                hash[out]--;//出窗口
                if(hash[out] == 0) {
                    kinds--;
                }
                left++;
            }
            //更新结果
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }
}

六.找到字符串中所有字母异位词

1.题目解析

2.算法原理

因为字符串p的异位词的长度一定与字符串p的长度相等，所以我们可以在字符串s中构造一个长度为与字符串p的长度相同的滑动窗口，并在滑动中维护窗口中维护窗口中每种字母的数量
当窗口中每种字母的数量与字符串p中每种字母的数量相同时，则说明当前窗口为字符串p的异位词
因此可以用两个大小为26的数组来模拟哈希表，一个来保存s中的子串每个字符出现的个数，另一个来保存p中每一个字符出现的个数。这样就能判断两个串是否是异位词

固定的滑动窗口

方法一 先使用hash1数组（数组模拟哈希表）来统计p数组中每个字符的出现个数再使用hash2数组（数组模拟哈希表）来统计窗口中（s数组中）字符的出现个数

进窗口：将s数组中依次在hash2表中进行记录
判断条件：当固定窗口right-left+1的长度大于p数组的长度时说明窗口大小超出范围
出窗口：将left++，并将其在hash2数组中统计的个数--
更新：判断hash1和2两个数组是否相同即可

方法二 利用count来统计窗口中有效字符的个数 定义好count变量，只需判断count变化的条件即可

进窗口：当我们将s数组中窗口的内容在hash2中依次进行统计，统计前我们要判断是否要更新count变量

判断条件

出窗口

更新结果只有当count == m时条件才成立，我们将left添加到list中即可 if(count == m) ret.add(left);

注意：进窗口时是先统计个数再判断更新count，而出窗口时是先判断更新count再改变个数

3.编写代码

class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        //统计p数组中每个字符的出现个数
        int[] hash1 = new int[26];
        for(char ch:p) hash1[ch - 'a']++;  //找到字符在数组中的位置 0-a 1-b 3-c
        //统计窗口每个字符的出现个数
        int[] hash2 = new int[26];
        int m = p.length;

        for(int left = 0,right = 0;right < s.length;right++) {
            //1.进窗口
            char in = s[right];
            hash2[in - 'a']++;//hash2数组中下标的位置就表示对应的元素 下标对应的元素为0则存在，为1则不存在

            //2.判断
            if(right - left + 1 > m) {
                //3.出窗口
                char out = s[left++];
                hash2[out - 'a']--;
            }
            //4.更新
            if(Arrays.equals(hash1,hash2)) {
                ret.add(left);
            }
        }
        return ret;
    }
}

class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();
        //将字符串强转为数组以方便统计
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        //统计字符串p中各个元素出现的个数
        int[] hash1 = new int[26];
        for(char ch : p) hash1[ch - 'a']++;  //a-0 b-1

        int[] hash2 = new int[26];
        int m = p.length;

        for(int left = 0,right = 0,count = 0;right < s.length;right++) {
            //利用变量count来统计窗口中“有效字符的个数”

            //1.进窗口
            char in = s[right]; //记录进窗口时right位置下的字符
            hash2[in - 'a']++;
            if(hash2[in - 'a'] <= hash1[in - 'a']) count++; //当hash2数组中对应right的大小 < hash1中对应right的大小时，count++
            //2.判断条件
            if(right - left + 1 > m) {
                //3.出窗口
                char out = s[left++];
                if(hash2[out - 'a'] <= hash1[out - 'a']) count--; //先判断是否为有效字符  c c  此时count不变
                hash2[out - 'a']--;
            }
            if(count == m) ret.add(left);
        }
        return ret;
    }
}

七.串联所有单词的子串

1.题目解析

2.算法原理

该题目与上题找到字符串中所有字母异位词有异曲同工之妙，上题是判断字符而本题是用来判断字符串，与上题的不同点：

哈希表：本题需要创建hash<String,Integer>来统计字符串出现的次数
left和right指针的移动：因为题目中说明words中所有的字符串长度相同，所以指针移动的步长为words数组中字符串的长度
滑动窗口的执行次数：words[0].length次

3.编写代码

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        //存放返回值
        List<Integer> ret = new ArrayList<Integer>();
        //创建哈希表统计words中子串出现的频次
        Map<String,Integer> hash1 = new HashMap<String,Integer>();
        for(String str : words) hash1.put(str,hash1.getOrDefault(str,0)+1);//设置str对应的value   因为可能存在重复的子串所以要设置累加

        int len = words[0].length(),m = words.length;
        //外层循环设置滑动窗口执行次数
        for(int i = 0;i < len;i++) {
            //统计窗口内所有单词的频次
            Map<String,Integer> hash2 = new HashMap<String,Integer>();
            for(int left = i,right = i,count = 0;right + len <= s.length();right += len) {
                //1.进窗口并维护count
                String in = s.substring(right,right + len);
                //在hash2中更新对应的value
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;   //可能hash1中不存在in，所以hash1初值设定为0

                //2.判断条件
                //当窗口内字符串长度大于words中总字符的长度时
                if(right - left + 1 > len*m) {
                    //3.出窗口
                    String out = s.substring(left,left+len);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out) - 1);//更新out的频次
                    left += len;
                }
                //4.更新结果
                if(count == m) ret.add(left);
            }
        }
        return ret;
    }
}

八.最小覆盖字串

1.题目解析

2.算法原理

暴力解法：暴力枚举+哈希表 我们从s字符串的首字符依次遍历，从左往右依次寻找，找到后记录，接着寻找下一个

利用count来标记有效字符的种类 前置工作：我们将字符串转换为字符数组方便后续利用数组模拟哈希表来统计有效字符 ①进窗口并维护count：统计s数组中有效字符并记录在hash2中，记录后再维护count 当前字符个数hash1和hash2中相等则count++ ②判断条件更新结果：我们需要比较hash2中有效字符的种类和hash1中的种类count，所以我们需要在最开始统计字符串t中每个字符的频次时统计字符的种类kinds；当kinds==count时说明窗口内的元素种类满足情况，我们进行更新：记录长度minlen = right - left + 1并记录当前窗口内首元素的位置即begin = left（提前定义minlen为Integer.MAX_VALUE，begin = -1） ③出窗口并维护count：left向后移动一位，当移动的当前元素在两个哈希表中都相同时说明出窗口移除的是有效字符，此时count--，维护完count后我们更新此元素在哈希表中的个数最后我们返回字符串对应的起始位置和最后位置即可，使用substring方法记录并返回字符串，begin可能仍未-1返回空字符串即可

3.编写代码

class Solution {
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        //hash1统计字符串t中每一个字符的个数
        int[] hash1 = new int[128];
        int kinds = 0;//字符串t中有多少种字符
        for(char ch : t) {
            if(hash1[ch] == 0) kinds++;
            hash1[ch]++;
        }
        //统计窗口每个字符的出现个数
        int[] hash2 = new int[128];

        int minlen = Integer.MAX_VALUE,begin = -1;
        for(int left = 0,right = 0,count = 0;right < s.length;right++) {
            //1.进窗口
            char in = s[right];
            hash2[in]++;
            //维护count
            if(hash2[in] == hash1[in]) count++;
            //2.判断条件
            while(kinds == count){
                //3.更新结果
                if(right - left + 1 < minlen) {
                    minlen = right - left + 1;
                    begin = left;
                }
                //4.出窗口
                char out = s[left++];
                //维护count
                if(hash2[out] == hash1[out]) count--;
                hash2[out]--;
            }
        }
        if(begin == -1) return new String();
        else return ss.substring(begin, begin + minlen);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-26，如有侵权请联系 cloudcommunity@tencent.com 删除

统计