LeetCode_滑动窗口篇_leetcode 滑动窗口

作者：菜鸟追梦旅行 | 2024-03-21 00:01:57

踩

leetcode 滑动窗口

滑动窗口

滑动窗口可以理解为双指针的一种，左窗口l，右窗口r。

一般，右窗口r先行，达到阶段性分界点（题目要求条件或者限制），开始移动左窗口l。我们要在移动的过程中统计题目的答案。

如果求的是最大值, 外循环移动l, 内循环移动r统计最大值, 遇到分界条件后, 移动l后立即继续持续移动r统计最大值;

for(int left = 0, right = 0; left < len; left++) {
	while(right < len && right条件) {
		...
		right++;
	}
	...
}
1
2
3
4
5
6
7

如果求的是最小值, 外循环移动r, 内循环移动l, 遇到分解条件后, 持续移动l统计最小值;

for(int left = 0, right = 0; right < len; right++) {
	...
	// 判断是否满足条件，满足条件后开始回缩left；
	if(条件) {
		while(left < len && left条件) {
			...
			left++;
		}
	}
}
1
2
3
4
5
6
7
8
9
10

求最小值同样也可以外循环移动l，内循环移动r。每一个left，都通过right遍历探索条件，满足条件后，再收缩left。

for(int left = 0, right = 0; left < len; left++) {
	while(right < len && right条件) {
		...
		right++;
	}
	...
	// 回缩left
	while(条件) {
		left++;
	}
}
1
2
3
4
5
6
7
8
9
10
11

在这里插入图片描述

209.长度最小的子数组

在这里插入图片描述

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 当前遍历的子数组总和
        int sum = 0;
        // 最小子数组的长度
        int min = Integer.MAX_VALUE;
        // 右窗口先行滑动
        for(int l = 0, r = 0; r < nums.length; r++) {
            // 遍历的元素加入子数组
            sum += nums[r];
            // 达到题目条件，子数组总和sum>target，记录最小子数组长度，并开始移动左窗口，探索更小的子数组。
            while(sum >= target) {
                min = Math.min(min, r - l + 1);
                // 左窗口移动，移除子数组中起始的元素。
                sum -= nums[l++];
            }
        }

        // 如果未有满足条件的子数组，min应该未改变过，返回题目要求0。
        return min == Integer.MAX_VALUE? 0 : min;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.无重复字符的最长字串

在这里插入图片描述

class Solution {
    // 滑动窗口 
    // 这道题目求的是最大值
    public int lengthOfLongestSubstring(String s) {
        // 辅助Set，判断当前遍历元素是否重复
        Set<Character> set = new HashSet<>();
        int max = 0;
        
        // 这里同样是先行移动右窗口，右窗口的移动是在内部循环，左窗口的移动在外循环
        for(int l = 0, r = 0; l < s.length(); l++) {
            // 先行移动右窗口，直到遇到子数组中重复元素或越界。
            while(r < s.length() && !set.contains(s.charAt(r))) {
                // 加入遍历集合
                set.add(s.charAt(r));
                // 计算最大值
                max = Math.max(max, r - l + 1);
                r++;
            }
            // 右窗口遇到分界条件后,开始移动左窗口,但是因为探索的是最大值,我们将左窗口移动一次后,继续探索右窗口,而不是持续的移动左窗口缩小边界;
            set.remove(s.charAt(l));
        }

        return max;
    }
}
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

76.最小覆盖字串（困难）

在这里插入图片描述
这里给了两种写法：

1.外循环left，内循环right

class Solution {
    /**
     * 滑动窗口
     * 外循环left，内循环right。每到一个新left，开始向右遍历right，直到满足覆盖条件。再右移一次left，判断是否覆盖，若不覆盖继续开始向右循环right。
     * 通过一个HashMap与目标字符串长度，共同记录判断是否满足覆盖子串条件
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        Map<Character, Integer> tarMap = new HashMap<>();
        for(int i = 0; i < t.length(); i++) {
            tarMap.put(t.charAt(i), tarMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        int right = 0;
        // HashMap记录目标字符出现的次数，tarCount记录字符总数。当字符总数为0时，即为覆盖子串。
        int tarCount = t.length();
        String res = "";
        // 外循环left
        for(int left = 0; left < s.length(); left++) {
            // 内循环right
            // 每一个left都判断当前是否覆盖子串，若不覆盖则向右遍历right，直到覆盖。
            while(right < s.length() && tarCount > 0) {
                // 当前right指向字符是否为目标字符
                if(tarMap.containsKey(s.charAt(right))) {
                    // 若为目标字符，当前出现次数是否超过目标次数
                    if(tarMap.get(s.charAt(right)) > 0) {
                        // 若没超过目标次数，则目标总数-1；
                        tarCount -= 1;
                    }
                    // 目标字符出现次数 - 1；
                    tarMap.put(s.charAt(right), tarMap.get(s.charAt(right)) - 1);
                }
                // right右移
                right++;
            }
            // 若right已经出界且目标总数没有达到，则break退出。
            if(right == s.length() && tarCount > 0) {
                break;
            }
            // 准备右移left
            if(tarMap.containsKey(s.charAt(left))) {
                // 若left为目标字符，且右移后目标字符出现次数达不到要求，则判断当前状态是否为最小覆盖范围
                if(tarMap.get(s.charAt(left)) + 1 > 0) {
                    if(res == "" || res.length() > right - left) {
                        res = s.substring(left, right);
                    }
                    // 目标总数+1
                    tarCount++;
                }
                // 目标字符出现次数+1
                tarMap.put(s.charAt(left), tarMap.get(s.charAt(left)) + 1);  
            }
        }

        return res;
    }
}
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

2.外循环right，内循环left

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> tarMap = new HashMap<>();
        for(int i = 0; i < t.length(); i++) {
            tarMap.put(t.charAt(i), tarMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        // HashMap记录目标字符出现的次数，tarCount记录字符总数。当字符总数为0时，即为覆盖子串。
        int tarCount = t.length();
        String res = "";
        // 外循环right
        for(int left = 0, right = 0; right < s.length(); right++) {
            if(tarCount > 0) {
                // 当前right指向字符是否为目标字符
                if(tarMap.containsKey(s.charAt(right))) {
                    // 若为目标字符，当前出现次数是否超过目标次数
                    if(tarMap.get(s.charAt(right)) > 0) {
                        // 若没超过目标次数，则目标总数-1；
                        tarCount -= 1;
                    }
                    // 目标字符出现次数 - 1；
                    tarMap.put(s.charAt(right), tarMap.get(s.charAt(right)) - 1);
                }
                // right右移
            } else {
                continue;
            }

            
            while(left <= right && tarCount == 0) {
                // 准备循环右移left
                if(tarMap.containsKey(s.charAt(left))) {
                    // 若left为目标字符，且右移后目标字符出现次数达不到要求，则判断当前状态是否为最小覆盖范围
                    if(tarMap.get(s.charAt(left)) + 1 > 0) {
                        if(res == "" || res.length() > right - left + 1) {
                            res = s.substring(left, right + 1);
                        }
                        // 目标总数+1
                        tarCount++;
                    }
                    // 目标字符出现次数+1
                    tarMap.put(s.charAt(left), tarMap.get(s.charAt(left)) + 1);  
                }
                left++;
            }
            
        }

        return res;
    }
}
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

15.三数之和（向内的滑动窗口）

在这里插入图片描述
三数之和思想是双指针扩散，但在定义时由于题意是三元组，所以需要定义三个指针分别指向三个元素，一个指针进行遍历，每一次遍历中另外两个指针进行扩散。

双指针扩散思想

为了方便去重的判断，我们首先将元素按序排列。之后，使用三个指针left, middle, right分别从前向后指向三个元素。left为遍历的左边界，middle，right为扩散指针，每轮middle = left + 1, right = numsl.length - 1，三元组和为sum = nums[left] + nums[middle] + nums[right]。若当前sum < 0，middle++; 若当前sum > 0，right--；两个指针按照sum的值进行循环扩散，直到指针相撞left == right，且在这期间遇到sum == 0的情况，要记录nums[left], nums[middle], nums[right]的值。

这里强调三点：
1.每一轮遍历，两个扩散指针都要将边界范围内的值全部覆盖到，直到指针相撞，这是因为要记录所有可能的情况。
2.扩散指针去重：当sum == 0时，要考虑去重，即nums[middle] == nums[middle + 1],nums[right] == nums[right - 1]，将sum == 0的结果保持唯一性。
3.左指针遍历去重：上一个去重是在左边界确定的情况下保证另外两个元组的唯一性，那么左边界值等于上一轮左边界值得情况即nums[left] == nums[left - 1]，左边界值如果出现过，就无需再进行扩散了，因为这样是重复的扩散。

public List<List<Integer>> threeSum(int[] nums) {
    // 遍历 + 双指针,left用来遍历和确立左边界,middle和right用来扩散
    int left, middle, right;

    List<List<Integer>> res = new ArrayList<>();
    // 先排序
    Arrays.sort(nums);
    // 左边界遍历
    for(left = 0; left < nums.length - 2; left++) {
        // 左边界去重
        if(left > 0 && nums[left] == nums[left - 1]) {
            continue;
        }
        // 扩散
        middle = left + 1;
        right = nums.length - 1;
        // 一定要扩散到两个指针碰撞,即边界内所有元素都判断到
        while(middle < right) {
            int sum = nums[left] + nums[middle] + nums[right];
            if(sum < 0) {
                middle++;
            } else if(sum > 0) {
                right--;
            } else {
                List<Integer> sub = new ArrayList<>();
                sub.add(nums[left]);
                sub.add(nums[middle]);
                sub.add(nums[right]);
                res.add(sub);
                // sum == 0, 要进行扩散指针的去重
                while(middle < right && nums[middle + 1] == nums[middle]) {
                    middle++;
                }
                while(middle < right && nums[right - 1] == nums[right]) {
                    right--;
                }
                // 重要:记录三元组后,要继续移动双指针,为了覆盖所有的边界元素!
                // 经过扩散指针的去重操作后,扩散指针指向的元素不存在还有其他匹配的元素了,所以只需继续向内移动指针就好(只移动一个指针也可以,目的就是为了覆盖边界内全部元素).
                middle++;
                right--;    
            }
        }


    }

    return res;
}
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

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】