当前位置：首页 > article >正文

【算法】滑动窗口(下)

article 2025/2/26 21:30:35

水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

题目描述：

你正在探访⼀家农场，农场从左到右种植了⼀排果树。这些树⽤⼀个整数数组 fruits 表⽰，其中

fruits[i] 是第 i 棵树上的⽔果种类。

你想要尽可能多地收集⽔果。然⽽，农场的主⼈设定了⼀些严格的规矩，你必须按照要求采摘⽔果：

• 你只有两个篮⼦，并且每个篮⼦只能装单⼀类型的⽔果。每个篮⼦能够装的⽔果总量没有限制。

• 你可以选择任意⼀棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘⼀个⽔果。采

摘的⽔果应当符合篮⼦中的⽔果类型。每采摘⼀次，你将会向右移动到下⼀棵树，并继续采摘。

• ⼀旦你⾛到某棵树前，但⽔果不符合篮⼦的⽔果类型，那么就必须停⽌采摘。

给你⼀个整数数组 fruits ，返回你可以收集的⽔果的最⼤数⽬。

⽰例 1：

输⼊：fruits = [1,2,1]

输出：3

解释：

可以采摘全部 3 棵树。

⽰例 2：

输⼊：fruits = [0,1,2,2]

输出：3

解释：

可以采摘 [1,2,2] 这三棵树。

如果从第⼀棵树开始采摘，则只能采摘 [0,1] 这两棵树。

⽰例 3：

输⼊：fruits = [3,3,3,1,2,1,1,2,3,3,4]

输出：5

解释：

可以采摘 [1,2,1,1,2] 这五棵树

滑动窗口

解题思路：

本题关键也是【一段连续的子区间】，只不过这个子区间需要满足，一共有两种元素(水果)。然后找到最大的即可

我们这里选择使用数组hash来统计窗口内出现了多少种水果，使用计数器count统计区间内的水果种类

初始化窗口(进窗口)：满足窗口内有2种水果(临界)，我们采用数组hash来记录不同种类的水果个数。当该种类的水果在数组中未出现，计数器count++(水果种类+1)。

出窗口条件：当窗口内有大于2种水果

出窗口：左侧种类的水果个数进行减1(hash数组);当该种类的水果量为0时，count--;最后让left++。

处理结果：只需要找到最大的区间即可

解题代码：

class Solution {
        public static int totalFruit(int[] fruits) {
        int n=fruits.length;
        //当只有一棵树时
        if(n==1){
            return 1;
        }
        int sum=0;
        int count=0;//记录区间内元素种类
        int[] hash=new int[n];
        for(int left=0,right=0;right<n;right++){
            if(hash[fruits[right]]==0){
                count++;
            }
            hash[fruits[right]]++;//进窗口
            //记录hash数组中目前不为0的个数---子区间中元素的种类
            while(count>2){//出窗口条件
                int out=fruits[left];
                hash[out]--;
                if(hash[out]==0)count--;
                left++;//出窗口
            }
            sum=Math.max(sum,right-left+1);
        }
        return sum;
    }
}

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

题目链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的⼦串，返回这些⼦串的起始索引。不考虑答案

输出的顺序。

异位词指由相同字⺟重排列形成的字符串（包括相同的字符串）。

⽰例 1:

输⼊:

s = "cbaebabacd", p = "abc"

输出:

[0,6]

解释:

起始索引等于 0 的⼦串是 "cba", 它是 "abc" 的异位词。

起始索引等于 6 的⼦串是 "bac", 它是 "abc" 的异位词。

⽰例 2:

输⼊:

s = "abab", p = "ab"

输出:

[0,1,2]

解释:

起始索引等于 0 的⼦串是 "ab", 它是 "ab" 的异位词。

起始索引等于 1 的⼦串是 "ba", 它是 "ab" 的异位词。

起始索引等于 2 的⼦串是 "ab", 它是 "ab" 的异位词。

提⽰:

1 <= s.length, p.length <= 3 * 10^4

s 和 p 仅包含⼩写字⺟

题目分析：根据示例，我们可以知道，我们只需要在字符串s中找到一个长度与字符串p一致，且该区间内的字符在字符串p中都出现过。然后将此区间的起始索引添加到列表即可

滑动窗口

解题思路：

1.因为字符串p的异位词长度一定与字符串p的子字符串的长度相同，所以我们可以在字符串s中构造一个长度与字符串p的长度相同的滑动窗口，并在滑动中维护窗口中每种字符的数量

2.当窗口每种字符的数量与字符串p中每种字符的数量相同时，则说明当前窗口为字符串p的异位词

3.因此我们用两个数组来模拟哈希表，一个来保存字符串s的子串(窗口)中每个字符出现的个数，另一个保存字符串p中每一个字符出现的个数。在【一段连续子区间】中，只需要判断这个区间的字符是否都与字符串p中一致

简单来说，我们需要在保证窗口和字符串p在长度相等的同时还需要保证窗口内的字符和字符串p也一致

实现方式：

1.用两个数组分别记录字符串s和p的字符

·使用hash1数组记录字符串p中的字符

·使用hash2数组统计窗口中出现的字符

2.用count记录窗口内的字符和字符串p一致的个数

为了统计字符，我们这里把字符串都转化为char类型的数组

初始化窗口：如果当前字符出现在字符串p中，并且个数小于等于字符串p中的个数时，count++

出窗口条件：当窗口的长度大于字符串p时

出窗口：窗口内左侧的该元素的个数小于等于字符串p中的个数时，令count--，并减去该元素的个数

处理结果：当count==字符串p的长度时，将窗口的起始索引尾插进列表

解题代码：

class Solution {
        public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list=new ArrayList<>();
        int n=s.length();
        int m=p.length();
        int[] hash1=new int[26];//记录p字符串中哪几个字符
        char[] str=p.toCharArray();//把p字符串转换为字符
        //用hash数组记录p字符串中的字符
        for(char x:str){
            hash1[x-'a']++;
        }
        char[] arr=s.toCharArray();
        int[] hash2=new int[26];//统计窗口中每个字符出现的个数
        for(int left=0,right=0,count=0;right<n;right++){
            char ch=arr[right];
            ++hash2[ch-'a'];
            if(hash2[ch-'a']<=hash1[ch-'a'])count++;//进窗口
            if(right-left+1>m){//出窗口条件：当子数组长度大于p字符串的长度m时
                char out=arr[left];
                left++;
                if(hash2[out-'a']--<=hash1[out-'a']){
                    count--;
                }//出窗口
            }
            //更新结果
            if(count==m)list.add(left);
        }
        return list;
    }
}

串联所有单词的子串

题目链接：30. 串联所有单词的子串 - 力扣（LeetCode）

题目描述：

给定⼀个字符串 s 和⼀个字符串数组 words。 words 中所有字符串⻓度相同。

s 中的串联⼦串是指⼀个包含 words 中所有字符串以任意顺序排列连接起来的⼦串。

◦ 例如，如果 words = ["ab","cd","ef"]，那

么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联⼦

串。 "acdbef" 不是串联⼦串，因为他不是任何 words 排列的连接。

返回所有串联字串在 s 中的开始索引。你可以以任意顺序返回答案。

⽰例 1：

输⼊：s = "barfoothefoobarman", words = ["foo","bar"]

输出：[0,9]

解释：因为 words.length == 2 同时 words[i].length == 3，连接的⼦字符串的⻓度必须为 6。

⼦串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。

⼦串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。

输出顺序⽆关紧要。返回 [9,0] 也是可以的。

⽰例 2：

输⼊：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]

输出：[]

解释：因为 words.length == 4 并且 words[i].length == 4，所以串联⼦串的⻓度必须为 16。

s 中没有⼦串⻓度为 16 并且等于 words 的任何顺序排列的连接。

所以我们返回⼀个空数组。

⽰例 3：

输⼊：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

输出：[6,9,12]

解释：因为 words.length == 3 并且 words[i].length == 3，所以串联⼦串的⻓度必须为 9。

⼦串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。

⼦串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。

⼦串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提⽰：

1 <= s.length <= 104

1 <= words.length <= 5000

1 <= words[i].length <= 30

words[i] 和 s 由⼩写英⽂字⺟组成

题目解析：

我们只需在字符串s中找到一个子区间，使其包含了words数组中的所有字符串，并且长度=words数组长度*字符串长度(len)，然后将该子区间的起始索引添加到列表即可。

滑动窗口

为了判断窗口中的字符串是否与words数组中的一致，我们使用哈希表：

·hash1记录words数组中字符串

·hash2统计窗口内的字符串出现的个数

当然我们还需要让指针(right)每次移动的长度等于len

除此之外，我们还需要额外设置一个计数器count，用来记录窗口内的字符串与words数组中字符串相同的个数。

初始化窗口(进窗口)：在满足窗口长度小于等于[words数组长度*len]时，每次让长度为len的字符串进入窗口，如果该字符串出现在words数组中，则让count++

出窗口条件：当窗口长度大于[words数组长度*len]时

出窗口：当窗口长度大于[words数组长度*len]时，让最左侧长度为len的字符串出窗口，如果该字符串出现在words数组中，令count--

处理结果：当窗口长度恰好等于[words数组长度*len]并且count=words数组长度时，将该窗口的起始索引添加到列表中

但有一点例外，如下图：

由于我们每次让指针走的长度是words数组中字符串的长度，如果我们只进行一次循环，我们只能找到第一个ab，这样就不正确了。所以我们这里需要添加一个for循环，而且这个for循环的次数应该是words数组中字符串的长度。因为这样，在最后一次循环中，恰好是和第一次循环间隔一个字符串

解题代码：

class Solution {
      public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list=new ArrayList<>();
        Map<String,Integer> hash1=new HashMap<>();
        for(String str:words){
            hash1.put(str,hash1.getOrDefault(str,0)+1);
        }
        int len=words[0].length();
        int m= words.length;
      //执行次数
        for(int i=0;i<len;i++){
            Map<String,Integer> hash2=new HashMap<>();//保存窗口内所有单词的次数
            for(int left=i,right=i,count=0;right<=s.length()-len;right+=len){
                String in=s.substring(right,right+len);//截取[right,right+len)处的字符串
                hash2.put(in,hash2.getOrDefault(in,0)+1);//进窗口
                if(hash2.get(in)<=hash1.getOrDefault(in,0)) count++;
                if(right-left+1>len*m){ //出窗口条件
                    String out=s.substring(left,left+len);
                    if(hash2.get(out)<=hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out)-1);//出窗口
                    left+=len;
                }
                if(count==m) list.add(left);
            }
        }
        return list;
    }
}

最小覆盖子串

题目链接： 76. 最小覆盖子串 - 力扣（LeetCode）

题目描述：

给你⼀个字符串 s 、⼀个字符串 t 。返回 s 中涵盖 t 所有字符的最⼩⼦串。如果 s 中不存在涵盖 t 所

有字符的⼦串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的⼦字符串中该字符数量必须不少于 t 中该字符数量。

如果 s 中存在这样的⼦串，我们保证它是唯⼀的答案。

⽰例 1：

输⼊：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"

解释：

最⼩覆盖⼦串 "BANC" 包含来⾃字符串 t 的 'A'、'B' 和 'C'。

⽰例 2：

输⼊：s = "a", t = "a"

输出："a"

解释：

整个字符串 s 是最⼩覆盖⼦串。

⽰例 3:

输⼊: s = "a", t = "aa"

输出: ""

解释:

t 中两个字符 'a' 均应包含在 s 的⼦串中，

因此没有符合条件的⼦字符串，返回空字符串。

题目解析：

我们只需找到一个最小子串，使其涵盖了字符串t中的所有字符即可。

本题与前面题目有相似之处，如用数组记录字符、计数器统计窗口内元素与字符串一致的个数...等等

解题思路：

初始化窗口(进窗口)：用数组hash2统计窗口内字符出现的次数，如果该字符出现次数少于字符串中的字符，令count++

出窗口条件：当count大于等于字符串长度时

出窗口：让窗口左侧的字符次数减1，left++，如果该字符出现在字符串中，则令count--

处理结果：当count==字符串长度时，记录下窗口的左右两侧的索引

解题代码：

class Solution {
        public static String minWindow(String s, String t) {
        int n=s.length();
        int m=t.length();
        char[] ss=s.toCharArray();
        char[] tt=t.toCharArray();
        int[] hash1=new int[128];
        int[] hash2=new int[128];//统计窗口中出现的字符
        for(char x:tt){
            hash1[x]++;//记录字符串t中字符出现的次数
        }
        int leftIndex=-1;
        int rightIndex=-1;
        int min=Integer.MAX_VALUE;
        for(int left=0,right=0,count=0;right<n;right++){
            hash2[ss[right]]++;//进窗口
            if(hash2[ss[right]]<=hash1[ss[right]])count++;
            while(count>=m){//出窗口条件
                if(count==m){
                    if(right-left+1<min){
                        leftIndex=left;
                        rightIndex=right;
                        min=right-left+1;//处理结果
                    }
                }
                if(hash2[ss[left]]--<=hash1[ss[left]])count--;// 出窗口
                left++;
            }
        }
        if(rightIndex==-1)return "";
        else return s.substring(leftIndex,rightIndex+1);
    }
}

查看全文

http://www.kler.cn/a/562256.html