16数据结构与算法刷题之【滑动窗口】篇

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：

2、剑指offerII：

力扣总记录数：

加油加油！

leetcode

3. 无重复字符的最长子串【中等】

学习：leetcode题解

题目链接：3. 无重复字符的最长子串

题目内容：

速记：抓住重点最长、子串，则表名我们要找到连续且无重复的，这时候我们就可以使用滑动窗口来进行解决。

①set版本，使用集合开销较大。

②数组版本，限定在0-128之间，开销相对于set小。

思路：

1、滑动窗口（set方式）

思路：题目要求是最长子串，那么一定是连续的子串。这里要是想要时间复杂度为O(n)就需要使用到滑动窗口，规则如下：

这里我直接拿leetcode官方的示例：
以(a)bcabcbb开始的最长字符串为(abc)abcbb;
以a(b)cabcbb开始的最长字符串为a(bca)bcbb;
以ab(c)abcbb开始的最长字符串为ab(cab)cbb;
以abc(a)bcbb开始的最长字符串为abc(abc)bb;
以abca(b)cbb开始的最长字符串为abca(bc)bb;
以abcab(c)bb开始的最长字符串为abcab(cb)b;
以abcabc(b)b开始的最长字符串为abcabc(b)b;
以abcabcb(b)开始的最长字符串为abcabcb(b)。
思路：每个区间我们可以使用set来进行暂存，每进行移动窗口，将左边的一位进行移除，窗口中的依旧在set集合里不动，之后再去依次添加之后没出现过的元素。
1
2
3
4
5
6
7
8
9
10

复杂度分析：时间复杂度O(n)，空间复杂度O(∣Σ∣)：O(∣Σ∣)指的是字符集的大小，也就是默认为ASCII 码[0,128) 内的字符，默认128个，这里题目指的是数字、字母、空格。

public int lengthOfLongestSubstring(String s) {
    //哈希
    Set<Character> sets = new HashSet<>();
    //右边指针
    int right = -1;
    int maxLen = 0;
    //优化点：进行剪枝
    for (int i = 0; i < s.length() - maxLen; i++) {
        //滑动窗口右移，移除左边一个元素
        if (i != 0) {
            sets.remove(s.charAt(i - 1));
        }

        //若是在指定范围内&添加成功
        while (right + 1 < s.length() && sets.add(s.charAt(right + 1))){
            right++;
        }

        maxLen = Math.max(right - i + 1, maxLen);
    }
    return maxLen;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2、滑动窗口（数组）

思路：题目给定范围那么ASCII码的数字表示即为[0-128]之间，1表示在滑动窗口中的了，0表示还未添加。

代码：时间复杂度O(n)，空间复杂度O(∣Σ∣)

public int lengthOfLongestSubstring(String s) {
    //哈希
    int[] chars = new int[128];
    //右边指针
    int right = -1;
    int maxLen = 0;
    //优化点：进行剪枝
    for (int i = 0; i < s.length() - maxLen; i++) {
        //滑动窗口右移，移除左边一个元素
        if (i != 0) {
            chars[s.charAt(i - 1)] = 0;
        }

        //若是在指定范围内&添加成功
        while (right + 1 < s.length() && chars[s.charAt(right + 1)] == 0){
            chars[s.charAt(right + 1)] = 1;
            right++;
        }

        maxLen = Math.max(right - i + 1, maxLen);
    }
    return maxLen;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

滑动窗口的最大值【困难】

题目链接：滑动窗口的最大值

题目内容：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

思路1：双端队列来进行。【推荐】

• 时间复杂度：O(n)，数组长度为n，只遍历一遍数组。
• 空间复杂度：O(m)，窗口长度m，双向队列最长时，将窗口填满。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < k || nums.length == 0) {
            return new int[0];
        }
        int[] res = new int[nums.length - k + 1];
        int j = 0;
        //采用双端队列来解决
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        //1、第一个窗口
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.pollLast();
            }
            deque.addLast(nums[i]);
        }
        res[j++] = deque.peekFirst();
        //2、之后的窗口
        for (int i = k; i < nums.length; i++) {
            if (!deque.isEmpty() && deque.peekFirst() == nums[i - k]) {
                deque.pollFirst();
            }
            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.pollLast();
            }
            deque.addLast(nums[i]);
            res[j++] = deque.peekFirst();
        }
        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