一文讲完滑动窗口及经典题目

LeetCode643子数组平均最大数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public double findMaxAverage(int[] nums, int k) {
        int len = nums.length;
        int sum = 0;
        if (k > len || len < 1 || k < 1) {
            return 0;
        }
        // 先求出第一个窗口的和
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        
        int res = sum;
        for (int right = k; right < len; right++) {
            // 不可以只用sum一个变量，这样会累加 例如：0,4,0,3,2
            res = Math.max(res, sum += nums[right] - nums[right - k]);
        }
        return (double) res / k;
    }

LeetCode674最长连续递增数列

错误例子：忽视了可能接下来还有连续递增数列
重点：如果右侧元素比左侧元素小，需要重新记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
    int[] nums = {1,3,5,4,7};

    int lengthOfLCIS = findLengthOfLCIS(nums);
    System.out.println(lengthOfLCIS);
}
public static int findLengthOfLCIS(int[] nums) {
    int left = 0;
    int right = 1;
    int res = 1;
    int count = 1;
    while (right < nums.length) {
        if (nums[left] < nums[right]) {
            count++;
        }
        left++;
        right++;
        res = Math.max(res, count);
    }
    return res;
}

经过修改后变成这样，但是可能无法通过最后一个比较极端的测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int findLengthOfLCIS(int[] nums) {
        int left = 0;
        int right = 1;
        int res = 1;
        int count = 1;
        while (right < nums.length) {
            if (nums[left] < nums[right]) {
                count++;
            } 
            // 添加了一个else if 语句去判断
            else if (nums[left] > nums[right]) {
                count = 1;
            }
            left++;
            right++;
            res = Math.max(res, count);
        }
        return res;
    }

代码一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution { 
    public int findLengthOfLCIS(int[] nums) { 
        int res = 1; 
        if(nums.length == 1) return res; 
        int index = res; 
        for(int i = 0; i < nums.length - 1; i++){ 
            if(nums[i] < nums[i + 1]) { 
                index++; 
                res = Math.max(res,index); 
            } else { 
                res = Math.max(res,index); 
                index = 1; 
            } 
        } 
        return res; 
    }
}

代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findLengthOfLCIS(int[] nums) {
        int left = 0, right = 0;
        int res = 0;
        while (right < nums.length) {
            // 右侧元素比左侧元素小，重新记录left位置
            // 该问题的本质就是快慢指针，left就是slow指针
            if (right > 0 && nums[right - 1] >= nums[right]) {
                left = right;
            }
            right++;
            res = Math.max(res, right - left);
        }
        return res;
    }

最长子串专题

LeetCode3 无重复字符的最长子串

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

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。


寻找最长子串，必然要知道无重复字符串的首和尾，然后再确定最长的那一个，这样引出双指针，也就想到了滑动窗口。这里介绍一种经典的使用Map的思路。

定义一个K-V形式的map
注意如何设计k和v是重点
key：当前正在访问的字符串
value：下标索引值
每访问一个新元素，都将其下标更新成对应的索引值。
image.png

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) return 0;
    HashMap<Character, Integer> map = new HashMap<>();
    int max = 0;
    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        if (map.containsKey(s.charAt(right))) {
            left = Math.max(left, map.get(s.charAt(right)) + 1);
        }
        // 把字符对应索引放入
        map.put(s.charAt(right), right);
        max = Math.max(max, right - left + 1);
    }
    return max;
}

思路：
如上例子中的abcabc，第二次遇到a时，更新left到s.charAt(right)，这里的right所指向的就是字符’a’，可以理解为因为我们要找的是无重复的最长子串，这里出现了第二个a，我们就将第一个从范围中删去（也就是更新left的位置）
特殊情况：
例如 abba，回文串会导致left后退，这种情况不应该发生，
其实也不能说是特殊情况，因为一个字符串前面出现过的组合在后面可能还是会出现，此时可能会出现让left更新到字符第一次出现的位置导致left后退
第二次访问b时候，left更新是这样的：
left = map.get('b') + 1 = 2
第二次访问a时候，left更新是这样的：
left = map.get('a') + 1 = 1
其实这里依旧是上面红字的思路，去除掉重复的字符，但是如果left要回退说明现在left - right范围中没有这个重复的字符，因此left的更新有两种情况：

  1. 出现了重复字符，当前left - right 界定子串中含有当前字符，left更新：left = map.get(s.charAt(right)) + 1;
  2. 出现重复字符，但是当前left-right界定的子串中没有当前字符 : left = left;

代码：
left = Math.max(left, map.get(s.charAt(right)) + 1);

下面是笔者觉得讲解也不错的LeetCode有关left更新的讲解
LeetCode讲解要理解 left = Math.max(left,map.get(s.charAt(i)) + 1);需要回归到滑动窗口的原理上。
窗口中始终是无重复字母的字符串。 我们通过窗口的左界和右界控制窗口。
右界不用特意操作，因为它是+1，+1地涨上去，记得在循环里+1就好。
左界：每当有一个字符曾经出现过，就需要判断左界。
重点来了：
若，被判断的字符上一次出现的位置就在滑动窗口内，即 [ i，j ] 内， 则需要left改变位置，改变为该字符上次出现位置+1。也就是left = map.get(s.charAt(i)) + 1的情况。
例如：
abcdb中，窗口正常运行到abcd时，下一个字符为b，b上一次出现在实在窗口里，所以需要把left设置为上一次出现的位置+1的位置，得到新的窗口为cdb，不然你不这样设置，窗口里有重复的字符（bcdb），不符合窗口的定义。
若，不在滑动窗口内，则不用管。 不用管是因为：窗口中字符串没有重复字符。窗口符合定义。所以left = left。 left = left就表示这个窗口暂时不变。
Math.max(left,map.get(s.charAt(i)) + 1);无非是一种筛选在不在窗口内的具体筛选，表达形式罢了。
修改成以下形式也一样

1
2
3
4
5
6
7
8
9
//    l：左界下标
//    r：右界下标
if(map.get(s.charAt(i)) <= r && map.get(s.charAt(i)) >= l ){l
    left = map.get(s.charAt(i)) + 1;//在窗口内， map.get(s.charAt(i)) + 1
}
else if(map.get(s.charAt(i)) < l){
    left = left;//在窗口前，不变
}
else//tan 90°

我觉得写成这样虽然麻烦，但是能更清晰地表达原理。
个人认为面向求学者的题解都应该用这种让人一目了然的代码形式。
记得更新字符最新一次出现的位置 map.put(s.charAt(i),i);
因为我们要判断字符出现的位置是否在窗口内，如果被判断的符号一直在窗口外，无所谓更不更新。
但是，现实是
一旦被判断的字符就在窗口内，再用“过去的”，“以前的”的位置标记就不行了。
这回导致窗口内出现了重复字符，但没被检测出来的状况
所以必须用最新的位置，最新的位置能帮助我们判断该字符是否出现在窗口内。
上述方法也可以用滑动窗口思想来解决

LeetCode159 至多包含两个不同字符的最长子串

给定一个字符串s，找出 至多 包含两个不同字符的最长子串t，并返回该子串的长度。

1
2
3
输入: s = "eceba"
输出: 3 
解释: t是"ece"，长度为3.

依旧是滑动窗口，毕竟是一个系列的嘛，使用left和right来锁定一个窗口，然后一边向右移动一边分析，
这里用：aabbcccd为例
image.png
思考点：

  1. 怎么判断只有两个元素？

用Hash！！！每一个时刻，这个hashmap包括不超过三个元素。

  1. 移除的时候移除谁？移除只有left更新为什么？

把字符串里的字符都当作键，在窗口中的最右边的字符位置作为值。此时使用下面的代码就可以确定要删除谁，以及窗口left的新位置

1
2
del_index = Collections.min(haspmap.values());
left = del_index + 1;

看图理解一下：
image.png
代码如下：

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
public int lengthOfLongestSubstringTwoDistinct(String s) {
    if (s.length() < 3) {
        return s.length();
    }
    int left = 0, right = 0;
    HashMap<Character, Integer> hashmap = new HashMap<>();
    int maxLen = 2;
    while (right < s.length()) {
        //如果元素小于3个
        if (hashmap.size() < 3) {
            hashmap.put(s.charAt(right), right++);
        }
    
        //如果大小达到3个
        if (hashmap.size() == 3) {
            // 最左侧要删除的位置
            int del_idx = Collections.min(hashmap.values());
            hashmap.remove(s.charAt(del_idx));
            left = del_idx + 1;
        }
    
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}


LeetCode340 至多包含k个不同字符的最长子串

给定一个字符串s，找出至多包含k个不同字符的最长子串t

示例输入: s = “eceba”
输出: 3
解释: t是”ece”，长度为3.
本题和上面一题几乎没有区别，将判断hash大小为2改成k就可以，超过2就是k+1.

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
public int lengthOfLongestSubstringTwoDistinct(String s, int k) {
    if (s.length() < k + 1) {
        return s.length();
    }
    int left = 0, right = 0;
    HashMap<Character, Integer> hashmap = new HashMap<>();
    int maxLen = k;
    while (right < s.length()) {
        //如果元素小于3个
        if (hashmap.size() < k + 1) {
            hashmap.put(s.charAt(right), right++);
        }
    
        //如果大小达到3个
        if (hashmap.size() == k + 1) {
            // 最左侧要删除的位置
            int del_idx = Collections.min(hashmap.values());
            hashmap.remove(s.charAt(del_idx));
            left = del_idx + 1;
        }
    
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

长度最小的子数组

LeetCode209 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。**
找出该数组中满足其总和大于等于** target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。**如果不存在符合条件的子数组，返回 0 。
示例 1：

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

使用双指针，也可以视为队列法
本题基本思路：让元素不断入队，当入队元素和等于target时就记录一下此时队列的容量，如果队列元素之和大于target则开始出队，直到小于target则再入队。
如果出现等于target的情况，则记录一下此时队列大小，之后继续先入队再出队。每当出现元素之和等于target时我们就保留容量最小的那个。
出队：从左边出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right++];
            while (sum >= target) {
                min = Math.min(min, right - left);
                sum -= nums[left++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

盛水最多的容器

LeetCode11 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
笔者在一开始没有学习滑动窗口的时候是利用双指针思想，这里引入了滑动窗口让我更加理解这道题目，先看看笔者当时的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {

            if (height[left] <= height[right]) {
                max = Math.max(max, (right - left) * height[left++]);
            } else {
                max = Math.max(max, (right - left) * height[right--]);
            }

        }

        return max;
}

本题看似复杂，实际很简单。设置两个指针left，right，水槽板的高度为h[left]，h[right]，此状态下水槽面积为S(left,right)。
面积公式为：S(left,right) = min(h[left],h[right]) * (right - left)
这里最重要的是短板，它决定的水槽的高度上限，所以我们每次循环都移动短板并更新面积最大值

1
2
3
4
5
6
7
8
9
10
11
public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            max = height[left] < height[right] ?
            Math.max(max, (j - i) * height[left++]):
            Math.max(max, (j - i) * height[right--];
        }
        return max;
}

寻找子串异位词（排列）

如果两个字符串仅仅是字母出现的位置不一样，则称两者相互为对方的一个排列，也称为异位词。

LeetCode567 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1** **的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：

1
2
3
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").


解题思路

滑动窗口 + 字典
分析一： 题目要求 s1 的排列之一是 s2 的一个子串。而子串必须是连续的，所以要求的 s2 子串的长度跟 s1 长度必须相等。
分析二： 那么我们有必要把 s1 的每个排列都求出来吗？当然不用。如果字符串 a 是 b 的一个排列，那么当且仅当它们两者中的每个字符的个数都必须完全相等。
所以，根据上面两点分析，我们已经能确定这个题目可以使用 滑动窗口 + 字典 来解决。

我们使用一个长度和 s1 长度相等的固定窗口大小的滑动窗口，在 s2 上面从左向右滑动，判断 s2 在滑动窗口内的每个字符出现的个数是否跟 s1 每个字符出现次数完全相等。
我们定义 counter1 是对 s1 内字符出现的个数的统计，定义 counter2 是对 s2 内字符出现的个数的统计。在窗口每次右移的时候，需要把右边新加入窗口的字符个数在 counter2 中加 1，把左边移出窗口的字符的个数减 1。如果 counter1 == counter2 ，那么说明窗口内的子串是 s1  的一个排列，返回 True；如果窗口已经把 s2 遍历完了仍然没有找到满足条件的排列，返回 False。

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
public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return false;
    }

    //count1统计s1每个字符出现的次数
    int[] count1 = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        count1[s1.charAt(i) - 'a']++;
    }

    //count2 统计滑动窗口(大小固定)中各字母出现次数
    int[] count2 = new int[26];

    int left = 0, right = 0;
    while (right < s2.length()) {
        //窗口移动
        count2[s2.charAt(right) - 'a']++;
        right++;

        if (Arrays.equals(count1, count2)) {
            return true;
        }

        //当窗口达到最大容量的时候
        if (right - left == s1.length()) {
            count2[s2.charAt(left) - 'a']--;
            left++;
        }
    }
    return false;
}

上面是判断有没有，那接下来我们看看问你有几个的题目

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

给定两个字符串 s 和 p，找到 s** 中所有 p **的 **异位词 **的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
**异位词 **指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

本题思路和上面的几乎一模一样，唯一的不同是需要一个List，如果出现异位词，还要记录其开始位置，直接将其add到list中就可以了。

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
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();

    int[] count1 = new int[26];
    int[] count2 = new int[26];
    for (int i = 0; i < p.length(); i++) {
        count1[p.charAt(i) - 'a']++;
    }

    int left = 0;
    int right = 0;
    while (right < s.length()) {

        count2[s.charAt(right) - 'a']++;
        right++;

        if (Arrays.equals(count1, count2)) {
            res.add(left);
        }

        if (right - left == p.length()) {
            count2[s.charAt(left) - 'a']--;
            left++;
        }
    }
    return res;
}

image.png

滑动窗口的实际应用

滑动窗口算法在限流场景下有着广泛的应用，它可以帮助系统在一定时间内控制并发请求的数量，防止系统过载或崩溃。以下是滑动窗口算法在TCP传输原理以及一些常见的Java后台开发中的限流工具（如Sentinel和Hystrix）中的应用示例：

TCP传输原理中的滑动窗口

在TCP协议中，滑动窗口是一种流量控制机制，用于控制发送方发送数据的速率，以避免接收方处理不过来，从而导致丢包或网络拥塞。具体来说，发送方维护一个滑动窗口，其大小表示可以发送的数据量，而接收方维护一个接收窗口，其大小表示自己的缓冲区能够接受的数据量。发送方通过动态调整滑动窗口的大小，以适应网络状况和接收方的处理能力。

Sentinel和Hystrix中的滑动窗口

  1. Sentinel： Sentinel是一款开源的流量控制和熔断降级工具，它可以帮助开发者实现对应用程序的保护和限流。在Sentinel中，滑动窗口算法被用来限制每秒钟的请求数量或并发度。通过对请求的调用次数进行统计，Sentinel可以动态地调整滑动窗口的大小，从而控制流量，防止系统过载。
  2. Hystrix： Hystrix是Netflix开源的容错管理工具，用于防止分布式系统中的雪崩效应。在Hystrix中，滑动窗口算法被用于实现熔断机制。Hystrix会根据一段时间内的请求成功率或失败率来动态地调整滑动窗口的大小，当请求失败率超过阈值时，熔断器会打开，阻止请求进入系统，从而保护系统免受过多失败请求的影响。

滑动窗口的应用场景

滑动窗口算法在以上场景中的应用，体现了其对于流量控制和资源保护的重要作用。通过动态地调整窗口大小，系统可以根据当前的负载情况来控制流量，保护系统的稳定性和可靠性。在高并发场景下，滑动窗口算法能够有效地防止系统过载，提高系统的吞吐量和性能。

除了TCP传输原理和常见的Java后台开发中的限流工具外，滑动窗口算法还可以在许多其他领域和场景中应用。以下是一些示例：

  1. 流量控制：在网络通信中，例如HTTP服务器或消息队列，滑动窗口算法可以用于控制请求的速率，防止服务器过载或消息队列拥塞。
  2. 资源管理：在操作系统中，滑动窗口算法可以用于调度和管理系统资源，例如CPU时间片的分配和磁盘IO的调度。
  3. 数据库连接池：在数据库访问中，滑动窗口算法可以用于管理数据库连接池的并发访问数量，以避免数据库连接过多而导致资源耗尽。
  4. 缓存预热：在缓存系统中，滑动窗口算法可以用于控制缓存预热的速率，以平滑地预热缓存数据，避免突发的高并发请求导致缓存击穿。
  5. API限流：在微服务架构中，滑动窗口算法可以用于限制对API的请求频率，保护后端服务免受过多请求的影响。
  6. 任务调度：在分布式系统中，滑动窗口算法可以用于任务调度和负载均衡，动态地调整任务的分配和执行顺序，以保证系统的高可用性和性能。

这些示例说明了滑动窗口算法在各种不同领域和场景中的广泛应用，它是一种非常实用且灵活的流量控制和资源管理工具。