滑动窗口算法

大家好呀，我是小笙！本节我来介绍一下滑动窗口算法

滑动窗口

1.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target，找到数组中连续数组值和大于这个这个正整数的最小长度是多少？

给个例子

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组
1
2
3

滑动窗口适合解决在一堆数中或者字符中找到满足条件的值或者字符的最小长度或者是最长长度（而且必须是连续的）

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 记录窗口的左右边界
        int left = 0,right = 0;
        // 移动左边界的条件 ≥ target 
        int sum = 0;
        // 记录结果 最小长度
        int len = Integer.MAX_VALUE;

        for(int i=0;i<nums.length;i++){
            // 右边界在扩展
            sum += nums[right];
            // 满足左边界缩减的条件
            while(sum >= target){
                if(len > right-left+1){
                    len = right-left+1;
                }
                sum -= nums[left++];
            }
            right++;
        }
        return len == Integer.MAX_VALUE?0:len;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度（在一定范围内找连续的最长长度，就能尝试用动态规划来解决）

// 例子
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
1
2
3
4

暴力解法，代码刚通过的样子，待我梳理一下代码冗余以及添加一些注释

class Solution {
    public int longestValidParentheses(String s) {
        if(s.length() == 0){
            return 0;
        }
        // 滑动窗口左右边界
        int left = 0,right = 0;
        // 有效最长长度
        int len = 0;
        // 记录括号的状态 +1 左括号 -1 右括号 当状态值小于0 || （状态值>0 && 达到最后一个字符）
        int status = 0;

        for(;right<s.length();right++){
            char ch = s.charAt(right);
            if(')' == ch){
                status--;
            }else{
                status++;
            }
            
            if(status == 0  && len < right - left + 1){
                len = right - left + 1;
            }else if(status < 0){
                left = right + 1;
                status = 0;
            }
        }
        if(status > 0){
            status = 0;
            int l = s.length()-1,r = s.length()-1;
            while(--right >= left){
                l = right;
                char ch = s.charAt(right);
                System.out.println(ch);
                if(')' == ch){
                    status++;
                }else{
                    status--;
                }
                if(status == 0  && len < r - l + 1){
                    len = r - l + 1;
                }else if(status < 0){
                    r = l - 1;
                    status = 0;
                }
            }
        }
        return len;
    }
}
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

优化成果：讲两次循环内嵌，减少大量的重复代码，运行效率从 64ms -> 1ms 整理代码的重要性！！！

// 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：39.5 MB, 在所有 Java 提交中击败了99.90%的用户
class Solution {
    public int longestValidParentheses(String s) {
        int size = s.length();
        // 滑动窗口左右边界
        int left = 0,right = 0;
        // 有效最长长度
        int len = 0;
        // 记录括号的状态 +1 左括号 -1 右括号 0 比较当前长度
        // 当状态值小于0 || （状态值>0 && 达到最后一个字符） 有特定操作
        int status = 0;

        for(;right<size;right++){
            status = s.charAt(right) == ')'?status-1:status+1;
            
            if(status == 0  && len < right - left + 1){  // 状态为 0 
                len = right - left + 1;
            }else if(status < 0){  // 当状态值小于0
                left = right + 1;
                status = 0;
            }else if(status > 0 && right + 1 == size){ // 状态值>0 && 达到最后一个字符
                // 注意原来的状态大于 0,最后大于0状态内的长度都无法获取（只要我们进行反向寻找，必然最后的状态是小于0）
                // 状态清 0,该情况就是最后一个有效长度无法获取导致的
                status = 0;
                int l = size,r = size-1;
                while(--l >= left){
                    // 注意需要记录括号的状态 -1 左括号 +1 右括号 0 比较当前长度（因为是反向滑动窗口,括号是镜像）
                    status = s.charAt(l) == '('?status-1:status+1;
                    if(status == 0  && len < r - l + 1){
                        len = r - l + 1;
                    }else if(status < 0){
                        r = l - 1;
                        status = 0;
                    }
                }
            }
        }
        return len;
    }
}
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

3.最小覆盖子串

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

相对上面这题，这个就是字符的例子（会更加负责许多）

我的代码的实现只能解决子串是不能重复的时候才可以，因为Map会进行覆盖导致问题的出现；虽然是有问题的，但是我觉得是有思想的，所以我也拿出来分享一下，其实是有滑动窗口思想的雏形，只不过很少接触过滑动窗口

class Solution {
    public String minWindow(String s, String t) {
        if(s.contains(t)){
            return t;
        }
        // 记录最小字串的左右下标
        int[] indexs = new int[2];
        int[] minIndexs = new int[2];
        // 记录最小子串的长度
        int min = Integer.MAX_VALUE;
        // 删除字符高效
        StringBuilder str = new StringBuilder(t);
        // 用来记录t中存在的字符出现在s字符串中的下标
        Map map = new HashMap<>();


        for(int i=0;i value){
                            indexs[0] = value;
                        }
                        if(indexs[1] <= value){
                            indexs[1] = value;
                        }
                    }
                    if(min > (indexs[1] - indexs[0])){
                        min = indexs[1] - indexs[0];
                        minIndexs[0] = indexs[0];
                        minIndexs[1] = indexs[1];
                    }
                }else{
                    int index = str.indexOf(ch + "");
                    if(index != -1){
                        str.delete(index,index+1);
                    }
                    map.put(ch,i);
                    indexs[0] = Integer.MAX_VALUE;
                    indexs[1] = Integer.MIN_VALUE;
                    for(Integer value:map.values()){
                        if(indexs[0] > value){
                            indexs[0] = value;
                        }
                        if(indexs[1] <= value){
                            indexs[1] = value;
                        }
                    }
                    if(str.length() == 0){
                        min = indexs[1] - indexs[0];
                        minIndexs[0] = indexs[0];
                        minIndexs[1] = indexs[1];
                    }
                }
            }
        }
        if(min != Integer.MAX_VALUE){
            return s.substring(minIndexs[0],minIndexs[1]+1);
        }else{
            return "";
        }

    }
}
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

模仿框架代码实现

class Solution {
    public String minWindow(String s, String t) {
        // map记录窗口中的符合条件的字符
        Map<Character,Integer> window = new HashMap<>();
        for(char c : t.toCharArray())
            need.put(c,need.getOrDefault(c,0)+1);
        
        // 滑动窗口记录 字符以及需要的对应的数量
        Map<Character,Integer> need = new HashMap<>();
        
        // 滑动窗口的左右边界
        int left = 0,right = 0;
        // 缩减窗口的判定条件
        int count = 0;
        // 用于结果的输出
        int start = 0;
        int len = Integer.MAX_VALUE;

        while(right < s.length()){
            char c = s.charAt(right);
            right++;
            // 判断是否完全包含子串中的某个字符
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(need.get(c).equals(window.get(c))){
                    count++;
                }
            }
            
            //缩减窗口的判定条件
            while(count == need.size()){
                if(right - left < len){
                    // 记录最短的子串
                    len = right - left;
                    start = left;
                }
                
                char d = s.charAt(left);
                left++;
                if(need.containsKey(d)){
                    // 如果随着缩减，出现没有包含子串的情况
                    if(need.get(d).equals(window.get(d))){
                        count--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
    }
}
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

终极版（太厉害，respect !!!）

向大佬致敬，真的很完美，至少在我心里是！

class Solution {
    public String minWindow(String s, String t) {
        char[] chars = s.toCharArray(), chart = t.toCharArray();
        int n = chars.length, m = chart.length;

        int[] hash = new int[128];
        for (char ch : chart) hash[ch]--;

        String res = "";
        for (int i = 0, j = 0, cnt = 0; i < n; i++) {
            hash[chars[i]]++;
            if (hash[chars[i]] <= 0) cnt++;
            while (cnt == m && hash[chars[j]] > 0) hash[chars[j++]]--;
            if (cnt == m)
                if (res.equals("") || res.length() > i - j + 1)
                    res = s.substring(j, i + 1);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

滑动窗口的框架

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    // 滑动窗口记录
    Map<Character, Integer> need = new HashMap<>();
    // 字符和对应字符出现的次数
    for (char c : t.toCharArray()) 
        need.put(c,need.getOrDefault(c,0)+1);

    // 总的窗口大小
    Map<Character, Integer> window = new HashMap<>();
    // 记录窗口的左右边界
	int left = 0, right = 0;
    // 判断窗口左边开始移动标志
	int valid = 0; 
    // 还有变量就是用于记录数据,具体根据题目来
    // ...

    // 结束滑动窗口的标志
	while (right < s.size()) {
    	// 右移窗口
    	right++;
    	// 进行窗口内数据的一系列更新
    	...
    
    	// 缩减窗口的标志
    	while (window needs shrink) {
        	// 左移窗口
        	left++;
        	// 进行窗口内数据的一系列更新
        	...
    	}
	}
}
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

总结

什么时候使用滑动窗口？

在有范围的一段数字或者字符中找到连续的最大或者最小的一段数字或者字符

那我们我们在写滑动窗口算法的时候需要想到那几个方面的问题？

1.记录滑动窗口所需要的集合或者数组？（根据题意来）

2.什么条件下需要缩容呢？

3.返回结果需要哪些数据的记录？（根据题意来）