👉 day05 滑动窗口

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

难度中等983

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

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

暴力解法

遍历s然后判断是否是字母异位词 , 最后返回结果集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res=new ArrayList<>();
        for(int x=0,y=p.length();y<=s.length();x++,y++){// sunstring() 左闭右开,  因此y 需要取到s.length()
            if(isAna(s.substring(x,y).toString().toCharArray(),p.toCharArray()))
                res.add(x);
        }
        return res;
    }
    boolean isAna(char[]chars1,char[]chars2){
        int []cnt1=new int[26];
        int []cnt2=new int[26];
        for(char c: chars1){
            cnt1[c-'a']++;
        }
        for(char c: chars2){
            cnt2[c-'a']++;
        }
        return Arrays.equals(cnt1,cnt2);
    }
}

暴力解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length()<p.length()) return new ArrayList<>();//p 比s 大  ,直接return
        List<Integer> res=new ArrayList<>();
        char[]chars1=s.toCharArray();
        int l=0,r=1;
        char[]chars2=p.toCharArray();
        while(r<=chars1.length){
            while(r-l<chars2.length) // 0~3(0,1 ,2 ) r=3 break  3 
                r++;
            int []cnt1=new int[26];
            int []cnt2=new int[26];
            for(int i=l;i<r;i++){//0 1 2
                cnt1[chars1[i]-'a']++;
            }
            for(char c: chars2){
                cnt2[c-'a']++;
            }
            if(Arrays.equals(cnt1,cnt2)) 
                res.add(l);
            l++;
            r++; 
        }
        return res;
    }
}

滑动窗口技巧

713.官方思路秒懂○注释详细○双指针滑窗 【附通用滑窗模板】 - 乘积小于 K 的子数组 - 力扣（LeetCode）

我写了一首诗，把滑动窗口算法变成了默写题 - 找到字符串中所有字母异位词 - 力扣（LeetCode）

我写了首诗，把滑动窗口算法算法变成了默写题 :: labuladong的算法小抄

大致逻辑如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

⭐滑动窗口模板

1️⃣第一个模板：适用于需要使用 [变量] 记录的情况

例题如713. 乘积小于 K 的子数组 - 力扣（LeetCode）

还有类似题目如 1004.最大连续1的个数 III

滑动窗口 + 变量计数模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int slidingWindow(int[] nums, int k) {
        //数组/字符串长度
        int n = nums.length;
        //双指针，表示当前遍历的区间[left, right]，闭区间
        int left = 0, right = 0;
        //定义变量统计 子数组/子区间 是否有效
        int sum = 0;
        //定义变量动态保存最大 求和/计数
        int res = 0;
        //右指针遍历到数组尾
        while (right < n) {
            //增加当前右指针对应的数值
            sum += nums[right];
            //当在该区间内 sum 超出定义范围
            while (sum > k) {
                //先将左指针指向的数值减去
                sum -= nums[left];
                //左指针右移
                left++;
            }
            //到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
            res = Math.max(res, right - left + 1);
            //移动右指针，去探索下一个区间
            right++;
        }
        return res;
    }
}

1004.最大连续1的个数 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int longestOnes(int[] nums, int k) {
        //思路：将题目目的转为：求连续子数组，要求长度最大，0 最多为k
        //用滑动窗口，让 右指针 一直右移，记录0 的个数，记录长度，当0 大于k，则左指针右移
        int n = nums.length;
        int left = 0;
        int right = 0;
        int zeros = 0;
        int len = 0;
        //右指针到头位置
        while (right < n) {
            if (nums[right] == 0) {
                zeros++;
            }
            //当 0 个数超了，让left 一直右移到满足
            while (zeros > k) {
                if (nums[left] == 0) {
                    zeros--;
                }
                left++;
            }
            //记录符合条件的长度
            len = Math.max(len, right - left + 1);
            //右指针右移
            right++;
        }
        return len;
    }
}

2️⃣第二个模板：适用于需要用 [哈希表] 记录的情况

类似题目诸如

滑动窗口 + 哈希表存储模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public String slidingWindow(String s, String t) {
        //创建两个哈希表，分别记录 [需要的] 和 [加入的]
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> map = new HashMap<>();
        //创建 [双指针] 和 [有效数量]
        int left = 0, right = 0;
        int valid = 0;

        //外层循环，供右指针遍历
        while(right < s.length()){
            //创建临时 c 字符，是移入 窗口 内的字符
            char c = s.charAt(right);

            //进行窗口一系列逻辑更新
            ...

                //判断左指针是否要右移即窗口收缩：有效数量足够满足条件
                /*  可能是规定的窗口大小超出了，可能是有效值数量达成了
         1.  while(valid == need.size())
         2.  while(right - left + 1 >= s1.length())      
         */           
                while(windows need shrink){
                    // 创建 d 是要移除窗口的字符
                    char d = s.charAt(left);
                    left++;

                    //进行窗口一系列逻辑更新
                    ...
                }

            //右指针右移
            right++;
        }
    }

}

567.字符串的排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        //滑动窗口 + 两哈希，始终保证窗口长度，当长度超了，左指针准备右移
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> map = new HashMap<>();

        //创建 [双指针] 和 [有效数量]
        int left = 0, right = 0;
        int valid = 0;

        //
        for(Character c : s1.toCharArray()){
            need.put(c, need.getOrDefault(c,0)+1);
        }
        //
        while(right < s2.length()){

            char c = s2.charAt(right);

            if(need.containsKey(c)){
                map.put(c,map.getOrDefault(c,0)+1);
                if(need.get(c).equals(map.get(c))){
                    valid++;
                }
            }

            //当凑齐了元素，还要判断长度
            while(right - left + 1 >= s1.length()){
                if(valid == need.size()){
                    return true;
                }
                char d = s2.charAt(left);
                if(need.containsKey(d)){
                    if(need.get(d).equals(map.get(d))){
                        valid--;
                    }
                    map.put(d,map.get(d)-1);
                }
                left++;
            }
            right++;
        }
        return false;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //滑动窗口 + 两哈希模板直接秒杀
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int right = 0;
        int valid = 0;
        List<Integer> list = new ArrayList<>();

        //
        for (Character ch : p.toCharArray()
            ) {
            need.put(ch, need.getOrDefault(ch, 0) + 1);
        }
        //
        while (right < s.length()) {
            char c = s.charAt(right);
            //镜像代码1
            if (need.containsKey(c)) {
                map.put(c, map.getOrDefault(c, 0) + 1);
                if (need.get(c).equals(map.get(c))) {
                    valid++;
                }
            }

            while (right - left + 1 >= p.length()) {
                if (valid == need.size()) {
                    list.add(left);
                }

                char d = s.charAt(left);

                left++;
                //镜像代码2
                if (need.containsKey(d)) {
                    if (need.get(d).equals(map.get(d))) {
                        valid--;
                    }
                    map.put(d, map.getOrDefault(d, 0) - 1);
                }
            }
            right++;
        }
        return list;
    }
}

713. 乘积小于 K 的子数组

思路

难度中等589

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

713.官方思路秒懂○注释详细○双指针滑窗 【附通用滑窗模板】 - 乘积小于 K 的子数组 - 力扣（LeetCode）

首先定义两个指针 left 和 right，后续遍历数组与记录用，

  1. 左右指针起始均在位置 0 ；用右指针遍历数组，每次循环中右指针右移一次；
  2. 移动过程中纪录从左指针到右指针路上的连续数的乘积为 mul；
  3. 如果乘积大于 k 了，则左指针右移，注意此处用的是 while 来使左指针右移，因为实际情况可能是：右指针最后右移一次指向了一个比较大的数使得 mul 不小于目标值，此时左指针需要右移多次才能使得 mul 刚小于 k；
  4. 最后用 ans 记录 mul 小于 k 时的数组组合；

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        //同样排除k为1的情况比如  [1,1,1] k=1
        if (k <= 1) {
            return 0;
        }
        int left = 0,right = 0,mul = 1,ans = 0; // 左右指针, 记录成绩mul , 记录结果 ans
        //用右指针遍历整个数组，每次循环右指针右移一次
        while(right<nums.length) {
            mul *= nums[right];//记录乘积
            while (mul >= k) { //当大于等于k，左指针右移并把之前左指针的数除掉
                mul /= nums[left];
                left++;
            }
            //每次右指针位移到一个新位置，应该加上 x 种数组组合：
            //  nums[right]
            //  nums[right-1], nums[right]
            //  nums[right-2], nums[right-1], nums[right]
            //  nums[left], ......, nums[right-2], nums[right-1], nums[right]
            //共有 right - left + 1 种
            ans += right - left + 1;
            //右指针右移
            right++;
        }
        return ans;
    }
}

为什么[left, right]子数组 共有 right - left + 1 种?

首先需要知道三点：

  1. right必须在子数组中存在，
  2. 并且子数组是连续的，
  3. [left,right]的长度是right-left+1，记为n。

接着我枚举一下[left, right]的子数组，可以分别是：

  • 长度为1的[right],
  • 长度为2的[right-1, right]，
  • 一直到长度为n的[left, left+1, ..., right-1, right] 这样子的n个子数组。

209. 长度最小的子数组

思路

难度中等1311

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

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

  • 本题与上一题类似

首先定义两个指针 left 和 right，后续遍历数组与记录用，

  1. 左右指针起始均在位置 0 ；用右指针遍历数组，每次循环中右指针右移一次；
  2. 移动过程中纪录从左指针到右指针路上的连续数的和 plus；
  3. 如果和plus 了，则左指针右移，注意此处用的是 while 来使左指针右移，
    • 因为实际情况可能是：右指针最后右移一次指向了一个比较大的数使得 plus 不小于目标值，此时左指针需要右移多次才能使得 plus刚大于等于k；
  4. 过程中维护res 作为长度最短数组的长度, 最终返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res=0x3f3f3f3f,l=0,r=0, plus=0;
        while(r<nums.length){
            plus+=nums[r];
            while(plus>=target){
                res=Math.min(r-l+1,res);
                plus-=nums[l++];
            }
            r++;
        }
        return res==0x3f3f3f3f?0:res;
    }
}

类似的题目:

😧76. 最小覆盖子串

难度困难2077

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

参考题解: labuladong 的算法小抄

算法流程:

  1. 增大窗口 ( 窗口左闭右开 , 方便计算的同时 , 可以很好的理解窗口中的元素的情况)
  2. 窗口符合条件
  3. 开始优化
  4. 得出结果

需要注意java 的HashMap 的API 以及包装类的问题:

  1. Java 的 Integer，String 等类型判定相等应该用 equals 方法而不能直接用等号 ==

  2. HashMap 的数据在更新的时候需要判断是否containsKey 以及value的问题

    比如:

    • window.put(c,window.containsKey(c)?window.get(c)+1:1);
    • window.put(d, window.get(d) - 1);
    • window.put(c,window.getOrDefault(c,0)+1);

这里我们以题目的样例为例子 , 分析一下窗口扩大以及收缩的过程

s = "ADOBECODEBANC", t = "ABC"

扩张 , 此时窗口还没有满足need的字符串 , 那么就是不断的扩张的过程 , 直到窗口中的内容变为ADOBEC , 此时刚好valid == need.size()

收缩 , 此时窗口满足了need的要求, 那么我们来收缩窗口 , 在第一次收缩中 , 窗口变为了DOBEC , 此时不满足need , 下一轮循环继续扩张

扩张 , 窗口扩张 , 直到变为``DOBECODEBA` , 此时窗口再次满足need的要求 , 继续收缩

收缩 , 窗口中元素DOBECODEBA 持续收缩(while循环) , 直到窗口中的元素变成了ODEBA , 此时缺少了一个 C

扩张 , 直到窗口中元素变成ECODEBANC

收缩 , 直到元素变为 ANC , 此时刚好循环结束 , 返回

在收缩的过程中维护满足valid要求的最短的子串 , 最后返回结果即可

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
   public String minWindow(String s, String t) {
        Map<Character,Integer> need=new HashMap(), window=new HashMap();
        for(char c:t.toCharArray()){
            need.put(c,need.containsKey(c)?need.get(c)+1:1);
        }
        int left=0,right=0;
        int start=0,len=0x3f3f3f3f; //表示字串的长度
        int valid=0;//valid变量表示窗口中满足need 条件的字符个数，如果valid 和need.size 的大小相同，则说明窗口已满足条件,已经完全覆盖了串 T。
        while(right<s.length()){ // 开始滑! 窗口到str末时结束，注意[left,right)左开右闭
            char c=s.charAt(right); //c 是即将移入窗口的字符
            right++; // 扩大窗口
            if(need.containsKey(c)){ // 进行窗口内数据的一系列更新
                window.put(c,window.containsKey(c)?window.get(c)+1:1);
                if(window.get(c).equals(need.get(c)))  //如果当前字符数量满足条件，则给valid++
                    valid++;
            }
            //缩小窗口:当满足条件的字符与所求字符集长度相等时，此时字符串包括了所有的所求字符
            while(valid==need.size()){
                if(right-left<len){ //判断字符串是否为最小，然后覆盖 , len 统计的是最小的长度
                    start=left;
                    len=right-left;
                }
                // d 是将要被移出窗口的字符
                char d=s.charAt(left);
                left++; // 缩小窗口
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len==0x3f3f3f3f?"": s.substring(start,start+len);
    }
}

567. 字符串的排列

难度中等746

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

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

套用模板 , 思路大致相同 ,

需要注意的是

  1. 本题的left 左移的条件是 right-left> needSize

  2. 当有效的字符的数量与need 的字符的种数相同时, 返回 true

    这里如果直接使用数组来统计 need 的个数, 需要统计的是字符的种数 ,

    例如

    • 比如 s1中有两个a , 那么在第一次添加的时候, valid就不会增加, 直接第二次的时候才会valid++ ,

      因此使用size 函数来统计 need 中的种数

    • 由于cpp 的解法 ,人家用的是 unorder_map , 直接用 nedd.size()即可

    • 如果使用HashMap 来统计need , 可以省去size() 方法

  3. 不必担心会有窗口中会有别的字符 , 因为只有是need 的字符才会被添加到 window中

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
        //给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
    public boolean checkInclusion(String s1, String s2) {
        if(s2.length()<s1.length()) return false;
        int needSize =s1.length();
        char[]need=new char[128];
        char[]window=new char[128];
        char[]str=s2.toCharArray();
        for (char c : s1.toCharArray()) {
            need[c]++;
        }
        int left=0,right=0,valid=0; //valid 用来记录 符合条件的字符的数量
        while(right<str.length){
            char c=str[right];
            right++;
            if(need[c]!=0){ // 说明需要c
                window[c]++;
                if(window[c]==need[c]){
                    valid++;
                }
            }
            while(right-left>=needSize){ //字符足够了, 接下来需要优化 子串
                if(valid==size(need)) // 刚好是一个子串,  注意全排列需要长度相等 , 比如 abc 显然不包括 ac 的全排列 ,
                    return true;
                char del=str[left];
                left++; // 缩小窗口
                if(need[del]!=0){
                    if(need[del]==window[del])
                        valid--;
                    window[del]--;
                }
            }
        }
        return false;
    }
    /**
    这里如果直接使用数组来统计 need 的个数, 需要统计的是字符的种数 , 比如  s1中有两个a  , 那么在第一次添加的时候, valid就不会增加, 直接第二次的时候才会valid++ , 因此, 使用size 函数来统计 need 中的种数 , 由于cpp 的解法 ,人家用的是 unorder_map , 直接用 nedd.size()即可 
     */
    int size(char[]chars){
        int res=0;
        for(char c:chars){
            if(c!=0)
                res++;
        }
        return res;
    }
}

cpp滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 判断 s 中是否存在 t 的排列
bool checkInclusion(string t, string s) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 在这里判断是否找到了合法的子串
            if (valid == need.size())
                return true;
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 未找到符合条件的子串
    return false;
}

643. 子数组最大平均数 I

难度简单262

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案

没什么坑, 简单题,

双指针+滑动窗口,

当注意元素的个数的计算是 r-l+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int l=0,r=0;
        double plus=0,res=Integer.MIN_VALUE;
        while(r<nums.length){
            plus+=nums[r];
            if((r-l+1)==k){
                res=Math.max(res,plus/(r-l+1)); //plus/(r-l+1)
                plus-=nums[l++];
            }
            r++;
        }
        return res;
    }
}// 13+ 53 = 55

718. 最长重复子数组

难度中等779

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度。

滑动窗口解法 - 最长重复子数组 - 力扣（LeetCode）

image-20220823000100609

非常好理解，想象两把尺子，错开之后比较相同的部分，找最长相同的串就好了

image-20220822235719423image-20220822235729820

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        return nums1.length<=nums2.length? findMax(nums1,nums2):findMax(nums2,nums1);
    }

    public int findMax(int[] nums1, int[] nums2){
        int max=0;
        int m=nums1.length,n=nums2.length;
        /**
        nums1,nums2中较短的数组不动，这里默认nums1，较长的数组滑动
        初始位置：nums2右边界挨着nums1左边界，nums2从左往右滑动
         */
        // 第一阶段：nums2从左往右滑动，两数组重合部分长度不断增加，重合部分长度len从1开始增加
        // 重合部分：nums1起点下标0，nums2起点下标n-len，
        for(int len=1;len<=m;len++){
            max=Math.max(max,maxLen(nums1,0,nums2,n-len,len));
        }
        // 第二阶段：nums2从左往右滑动，两数组重合部分长度不变，重合部分长度始终为nums1长度m
        //  重合部分：nums1起点下标0，nums2起点下标n-m，然后递减
        for(int j=n-m;j>=0;j--){
            max=Math.max(max,maxLen(nums1,0,nums2,j,m));
        }
        // 第三阶段：nums2从左往右滑动，两数组重合部分长度递减，重合部分长度始终为nums1长度m-i
        //  重合部分：nums1起点下标i，递增，nums2起点下标0
        for(int i=1;i<m;i++){
            max=Math.max(max,maxLen(nums1,i,nums2,0,m-i));
        }
        return max;
    }

    /**
    nums1中下标i开始，nums2中下标j开始，长度为len子数组中，最长公共子数组(注意要连续)长度
     */
    public int maxLen(int[] nums1,int i,int[] nums2,int j,int len){
        int count=0,res=0;
        for(int k=0;k<len;k++){
            if(nums1[i+k]==nums2[j+k]){
                count++;
            }else if(count>0){
                //进入到这个if判断体里面，说明当前 nums1[i+k]!=nums2[j+k],即之前的公共子数组不再连续，
                // 所以要记录最大值，同时将count置零
                res=Math.max(count,res);
                count=0;
            }
        }
        /**
        1，count>0,说明有公共子数组是以nums1[i+len-1],nums2[j+len-1]结尾的，
           上面最后一步for循环没有进入到else if判断题里面，所以最终结果要取当前count和res的最大值
        2，count=0，说明res已经更新过了，res即为最终结果
         */
        return count>0? Math.max(count,res):res;
    }
}