LeetCode算法思想之滑动窗口_滑动窗口leetcode 稀土掘金

前言

滑动窗口，可以称为固定间距的双指针（快慢指针＋固定步长）
由于它自己独特的性质，所以专门拿出来探讨（双指针指路）

应用场景：数组，字符串

先上东哥（https://labuladong.gitee.io/algo/）的模板（对于模板，可能会限制你的思维，但有时在你突然没有思路的时候有很有帮助）

/* 滑动窗口算法框架 */
void slidingWindow(string s) {
    HashMap<Character, Integer> window; // hashmap一般用来判断窗口内的字符是否有重复
    
    int left = 0, right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // 在最终的解法代码中不要输出，因为 IO 操作很耗时，可能导致超时
        System.out.println("window:"+"["+left+","+right+"]"); 
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            // 缩小窗口
            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

开撸

1.lc209 长度最小的数组

在数组篇已经介绍过，链接

2.lc643 子数组最大平均数I

lc643 链接

描述：

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数

示例：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75

Solution：
窗口大小固定，直接模拟即可（不需要模板）

public double findMaxAverage(int[] nums, int k) {
        int sum = 0;

        for(int i=0;i<k;i++)
        {
            sum += nums[i];
        }
        int resSum = sum;

        for(int i=0,j=i+k ; j < nums.length ; i++,j++)
        {
            sum -= nums[i];
            sum += nums[j];

            resSum = sum>resSum?sum:resSum;
        }
        return (double)resSum/k;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

lc3 链接

描述：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度

示例：

输入: s = “abcabcbb”
输出: 3

Solution：
(也是滑动窗口，看到重复要想到哈希表啊！)

public int lengthOfLongestSubstring1(String s) {
        HashSet<Character> hashset = new HashSet<>();

        int resLen = 0; // 设置初始最长字符串长度为0
        
        // 设置左右指针
        for(int left=0,right=0;right<s.length();left++)
        {
            // 如果不重复，就添加到哈希表中
            while(right<s.length() && !hashset.contains(s.charAt(right))  )
            {
                hashset.add(s.charAt(right));
                right++;
            }
            // 循环结束，就代表遇到了重复的，所以移除最开始的字母
            hashset.remove(s.charAt(left));
            // 记录此时的长度（此时right已经指向下一重复字符，所以长度直接r-l）
            resLen = Math.max((right-left),resLen);
        }
        return resLen;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4.1695. 删除子数组的最大得分

lc1695 链接

描述：

题目有点复杂，简单点说，给你一个正整数数组 nums ，求累加和最大的无重复元素的连续子数组，返回其累加和的值

示例：

输入：nums = [4,2,4,5,6]
输出：17

Solution:
(和lc3几乎一样，就多一个求和)

public int maximumUniqueSubarray(int[] nums) {
        HashSet<Integer> hashset = new HashSet<>();

        int resSum=0; // 记录最终的和
        int sum = 0;  // 记录临时（每一次）的和
        int len = nums.length;

        for(int i=0,j=0;j<len;i++)
        {
            // 第一次循环不用剔除最开始的数
            if(i!=0)
                sum -= nums[i-1];

            while( j<len && !hashset.contains(nums[j]) )
            {
                hashset.add(nums[j]);
                sum+=nums[j++];
            }
            resSum = Math.max(sum, resSum);
            hashset.remove(nums[i]);
        }
        return resSum;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5. lc76 最小覆盖字串

lc76 链接

描述：

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

示例：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”

Solution：

 public static  String minWindow(String s, String t) {
        //1.维护两个map记录窗口中的符合条件的字符以及need的字符
        Map<Character,Integer> window = new HashMap<>();
        Map<Character,Integer> need = new HashMap<>();

        // 先将字符串t中的字符存入need哈希表中
        for(int i=0;i<t.length();i++)
        {
            char ch = t.charAt(i);
            need.put(ch,need.getOrDefault(ch,0)+1);
        }

        int left = 0,right = 0; // 左右双指针
        //count记录当前窗口中符合need要求的字符的数量,当count == need.size()时即可shrik窗口
        int count = 0; 
        int start = 0; //start表示符合最优解的substring的起始位序
        int len = Integer.MAX_VALUE; //len用来记录最终窗口的长度，并且以len作比较

        //一次遍历找“可行解”
        while(right < s.length()){
            //更新窗口
            char c = s.charAt(right);
            right++; //窗口扩大
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                // 当前窗口拥有的字符及对应的数量和need一样时，count就加1
                if(need.get(c).equals(window.get(c))){
                    count++;
                }
            }
            //收缩窗口，找符合条件的最优解
            while(count == need.size()){
              // 找到最短len，并记录此时的开始索引start
                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

参考链接：
https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/yi-ge-mo-ban-miao-sha-10dao-zhong-deng-n-sb0x/