分享丨基础算法｜滑动窗口（应用场景+代码+原理）【多图】
画图小匠
1170
2024.09.07
2024.09.09
发布于 重庆
滑动窗口学习分享

  1. 滑动窗口

    1. 引入

    2. 代码示例

    3. 更多场景

      1. 统计某个元素的个数不超过某个值的最长子数组
      2. 不包含重复元素的最长子数组

    4. 概述

    5. 主要步骤

    6. 另一种 理解方式

滑动窗口

引入

寻找长度为3且其元素和小于或等于15的子数组个数

image-20240904154305048.png

当这个数组的长度比较长的时候，两重循环似乎有些吃力！我们能不能优化一下？

image-20240904162757493.png

整个过程实际上就像一个长度为3的窗口的在不断的向右移动，我们只要维护整个窗口里的元素和 就可以找到所有满足条件的子数组。

image-20240904173650465.png

代码示例

函数参数：

  • nums：输入数组
  • k：子数组长度
  • limit：限制条件，子数组和小于等于 limit
Java
Python
C++
class Solution {
    public int slidingWindows(int[] nums, int k, int limit) {
        int subArrSum = 0;      // 统计窗口中的元素和，即长度为k的子数组元素和
        int n = nums.length;
        // 统计首个子数组元素和，即构建滑动窗口
        for(int i = 0; i < k; i++){
            subArrSum += nums[i];
        }
        int res = subArrSum <= limit ? 1 : 0;   // 统计结果，这个就是判断条件 可以替换
        for(int i = k; i < n; i++){
            // 更新窗口元素和：1.加入当前元素 2.淘汰左侧元素，保证窗口维护的是[i-k+1, i]共k个元素
            subArrSum += nums[i] - nums[i-k];
            res += subArrSum <= limit ? 1 : 0;  // 统计结果，这个就是判断条件 可以替换
        }
        return res;
    }
}

更多场景

上面的引入是一个比较基础的场景，因为滑动窗口的尺寸是固定的。更多时候我们维护的滑动窗口的尺寸是不固定，而是伸缩的。

统计某个元素的个数不超过某个值的最长子数组

寻找子数组中元素3不超过3个的最长子数组

image-20240905111958439.png
image-20240905112008246.png

代码示例

函数参数：

  1. nums：输入数组
  2. k：统计的元素
  3. limit：子数组中元素出现的上限，即出现次数小于等于 limit
Java
Python
C++
class Solution {
    public int slidingWindows(int[] nums, int k, int limit) {
        int count = 0;                              // 统计元素k的个数
        int n = nums.length;
        int left = 0;                               // 滑动窗口左边界
        int res = 0;                                // 记录最长子数组长度，初始为最小值0
        for(int right = 0; right < n; right++){     // 滑动窗口右边界，右边界不断右移，往窗口加入更多元素
            count += nums[right] == k ? 1 : 0;
            if(count > limit){                      // 新加入元素导致窗口内k元素超过上限
                res = Math.max(res, right - left);  // [left, right)是一个满足条件的子数组
                while(count > limit){
                    count -= nums[left++] == k ? 1 : 0;     // 从窗口左边界依次淘汰元素，直到窗口内元素个数不超过limit
                }
            }
        }
        res = Math.max(res, n - left);               // 统计最后一个满足条件的子数组[left, n)
        return res;
    }
}

而这类题还可以简化：实际上我们的滑动窗口是在元素3的下标上进行滑动

image-20240905183643015.png

image-20240905184945731.png

滑动窗口维护的范围是一个开区间 (left, right)，区间长度为 3，即 right - left - 1 = 3。

Java
Python
C++
class Solution {
    public int slidingWindows(int[] nums, int k, int limit) {
        int n = nums.length;
        List<Integer> indexes = new ArrayList<>();  // 记录元素k的索引
        indexes.add(-1);                            // 初始加入一个前置位-1
        for(int i = 0; i < n; i++){
            if(nums[i] == k){
                indexes.add(i);                     // 记录每一个出现元素k的位置
            }
        }
        indexes.add(n);                             // 添加一个后置位n
        int res = 0;                                // 记录最长子数组长度，初始为最小值0
        for(int right = limit + 1; right < indexes.size(); right++){                        // right - left - 1 = limit, left最小为0则right最小为limit+1
            res = Math.max(res, indexes.get(right) - indexes.get(right - limit - 1) - 1);   // 滑动窗口范围为(left, right)，长度为limit，因此可以左边界left可以通过右边界right确定
        }
        return res;
    }
}

不包含重复元素的最长子数组

image-20240905202810638.png
image-20240905203031881.png

代码示例

函数参数：

  1. nums：输入数组
Java
Python
C++
class Solution {
    public int slidingWindows(int[] nums) {
        Set<Integer> set = new HashSet<>();   // 维护滑动窗口中的元素
        int left = 0;						// 滑动窗口左边界初始为0
        int res = 0;
        int n = nums.length;
        for(int right = 0; right < n; right++){			// 枚举滑动窗口右边界
            if(set.contains(nums[right])){				// 如果右边界的值已经在滑动窗口内容
                res = Math.max(res, right - left);       // 找到一个无重复元素的最长子数组
                while(set.contains(nums[right])){
                    set.remove(nums[left++]);            // 淘汰左边界的值直到将和右边界相同的值淘汰
                }
            }
            set.add(nums[right]);                   	// 经过处理后哈希表中没有右边界的值，加入哈希表
        }
        res = Math.max(res, n - left);   // 最后一个满足条件的子数组
        return res;
    }
}

概述

之所以把概述和步骤放在最后，是希望大家能在 充分理解滑动窗口的应用场景之后 再来阅读这些抽象性的总结性的文字（甚至你可以不看这部分自己总结！）

  1. 滑动窗口（Slide Window）是一种常用于 解决数组或字符串问题 的算法；
  2. 它通过在**O(n)的时间复杂度内遍历数据**来工作。
  3. 这种类型的算法通常使用两个指针（left和right）表示一个 窗口 的起始位置和结束位置，然后 根据需要 移动这两个指针 以获取所需的子集或子数组。

主要步骤

  1. 初始化（Initialize）：在开始时，设置两个指针left和right都指向数组的第一个元素。

  2. 条件检查（Condition Check）：确定窗口是否满足某个特定的条件【这一步是整个滑动窗口思想的 核心 / 关键】。

  3. 移动（Move）：根据条件判断的结果，决定如何移动指针以继续操作。【这就是为什么步骤2是关键：滑动窗口关键在滑动，而滑动关键在于条件判断输出如何滑动】

    1. 通常条件满足时我们移动右指针 right 加入元素到窗口中，条件不满足时我们移动左指针 left 从窗口中淘汰元素；
    2. 在代码上，我们可以每次强制移动右指针，然后移动左指针直到条件满足。相当于我们在找 以右指针指向元素 结尾的 满足条件的 最长子数组。

另一种 理解方式

当我们理解了上面的场景和文字之后，我们可以以另外一种角度来理解滑动窗口：我们枚举以每个元素 nums[i] 为结尾的最长子数组。

我们还是以【不包含重复元素的最长子数组】为例

image-20240907222038186.png

代码示例

这种理解角度对比之前的方式，代码会更简洁凝练一些。

Java
Python
C++
class Solution {
    public int slidingWindows(int[] nums) {
        Set<Integer> set = new HashSet<>();   // 维护滑动窗口中的元素
        int left = 0;						// 滑动窗口左边界初始为0
        int res = 0;
        int n = nums.length;
        for(int right = 0; right < n; right++){		// 枚举滑动窗口右边界
            while(set.contains(nums[right])){
                set.remove(nums[left++]);           // 淘汰左边界的值直到将和右边界相同的值淘汰
            }
            set.add(nums[right]);                   // 经过处理后哈希表中没有右边界的值，加入哈希表
            res = max(res, right - left + 1);       // 滑动窗口[left, right]就是一个以nums[right]结尾的满足条件的子数组
        }
        return res;
    }
}
评论 (1)