前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家 点击跳转到网站

一、算法简介

滑动窗口算法通过维护一个“窗口”，在数据结构上滑动该窗口来逐步处理数据，以解决特定类型的问题。窗口的大小可以根据问题的需要是固定的，也可以是可变的。其基本思想是在窗口内保持满足特定条件的元素子序列，然后通过不断移动窗口的左右边界来遍历整个数据结构，找到所需的结果。

二、算法原理

1. 初始化：设置左右指针left和right，通常都指向数据结构的起始位置。
2. 窗口滑动：
   • 扩展右边界：通常先移动right指针来扩展窗口的右边界，直到窗口内的元素不再满足特定条件或right指针到达数据结构的末尾。
   • 收缩左边界：在窗口不满足条件时，移动left指针来收缩窗口的左边界，直到窗口内的元素重新满足条件。
3. 记录结果：在窗口滑动的过程中，记录下满足条件的中间结果（如最大值、最小值、子串长度等）。
4. 重复步骤：重复步骤2和3，直到right指针遍历完整个数据结构。

三、经典例题

1. 长度最小的子数组

⭕ 题目链接：209. 长度最小的子数组

✅题目分析

在数组上滑动以寻找满足特定条件的最小子数组。窗口的左右边界（即left和right指针）根据当前窗口内元素的和与目标值的关系进行调整。

1. 初始化：设置两个指针left和right，都指向数组的起始位置。同时，初始化一个变量来记录当前窗口内元素的和（sum）。

2. 扩展窗口：通过移动right指针来扩展窗口，即向窗口中添加新的元素，并更新sum。

3. 判断条件：检查当前窗口内元素的和是否满足条件（例如，sum >= target）。

   • 如果满足条件，则尝试通过移动left指针来缩小窗口，同时更新结果（如记录当前窗口的长度，如果比已知的最小长度还小的话）。缩小窗口的过程是尝试找到满足条件的最小子数组。
   • 如果不满足条件，则继续扩展窗口（即继续移动right指针）。

4. 重复步骤：重复步骤2和3，直到right指针到达数组的末尾。

✅解题代码

class Solution  
{  
public:  
    // 函数用于找到和大于等于target的最小子数组的长度  
    int minSubArrayLen(int target, vector<int>& nums)  
    {  
        int n = nums.size(); // 获取数组长度  
        int sum = 0; // 用于存储当前窗口内元素的总和  
        int len = INT_MAX; // 初始化最小长度为整数的最大值，用于后续比较更新  
          
        // 初始化滑动窗口的左右指针  
        for(int left = 0, right = 0; right < n; right++)  
        {  
            sum += nums[right]; // 将当前右指针指向的元素加入窗口，并更新总和  
              
            // 当窗口内元素总和大于等于target时，开始尝试缩小窗口  
            while(sum >= target)  
            {  
                // 更新最小长度，如果当前窗口长度更新小于已知的最小长度，则  
                len = min(len, right - left + 1);  
                  
                // 缩小窗口，即将左指针指向的元素移出窗口，并更新总和  
                sum -= nums[left++];  
            }  
        }  
          
        // 如果len仍然是初始值INT_MAX，说明没有找到满足条件的子数组，返回0  
        // 否则返回找到的最小子数组的长度  
        return len == INT_MAX ? 0 : len;  
    }  
};

⭕为什么滑动窗口有效且时间复杂度低

• 避免重复计算：在每次调整窗口大小时，我们只需要从sum中加上或减去当前left或right指针所指向的元素值，而不需要重新计算整个窗口的和。这大大减少了计算量。
• 线性时间复杂度：尽管代码逻辑上看起来像是嵌套循环（一个循环控制left，一个控制right），但实际上每个元素最多被访问两次（一次作为right进入窗口，一次作为left离开窗口）。因此，总的时间复杂度是线性的，即O(N)，其中N是数组的长度。

四、相关题目

⭕ 3. 无重复字符的最长子串
⭕ 1004. 最大连续1的个数 III
⭕ 1658. 将 x 减到 0 的最小操作数
⭕ 904. 水果成篮
⭕ 438. 找到字符串中所有字母异位词
⭕ 30. 串联所有单词的子串
⭕ 76. 最小覆盖子串