算法沉淀——滑动窗口（leetcode真题剖析）-慈云数据

在这里插入图片描述

算法沉淀——滑动窗口

01.长度最小的子数组
02.无重复字符的最长子串
03.最大连续1的个数 III
04.将 x 减到 0 的最小操作数
05.水果成篮
06.找到字符串中所有字母异位词
07.串联所有单词的子串
08.最小覆盖子串
滑动窗口算法是一种用于解决数组或列表中子数组或子序列问题的有效技巧。它通过维护一个可变大小的窗口（通常是一个连续的子数组或子序列），在数据流中滑动该窗口来进行问题求解。这种方法在一维数组和二维数组中都有应用，并且在字符串处理中也很常见。
滑动窗口算法的基本思想是使用两个指针，通常是左指针（left）和右指针（right）来定义窗口，通过移动这两个指针，调整窗口的大小和位置，从而在不重复计算的情况下找到问题的解。

以下是滑动窗口算法的一般步骤：
1. 初始化窗口：定义左指针和右指针，并将窗口初始化为满足问题条件的初始状态。
2. 移动窗口：不断移动右指针，扩展窗口大小，直到不再满足问题条件为止。
3. 调整窗口：一旦窗口不再满足问题条件，开始移动左指针，缩小窗口大小，直到满足问题条件为止。
4. 记录解：在窗口移动的过程中，记录满足问题条件的解。
滑动窗口算法适用于一些问题，例如：
- 子数组和子序列的最大/最小值：在数组中找到满足条件的子数组或子序列的最大或最小值。
- 子数组和子序列的和或平均值：在数组中找到满足条件的子数组或子序列的和或平均值。
- 字符串处理问题：如找到最小覆盖子串、找到没有重复字符的最长子串等。
  下面我们通过几个真题来学习这个算法
  
  01.长度最小的子数组
  
  题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
  
  给定一个含有 n 个正整数的数组和一个正整数 target 。
  
  找出该数组中满足其总和大于等于 target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。
  
  示例 1：
```
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
```
  示例 2：
```
输入：target = 4, nums = [1,4,4]
输出：1
```
  示例 3：
```
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
```
  思路
  
  在最开始没接触这种算法题时，我们要先建立滑动窗口的概念，首先像这种题目要求是连续的情况下，我们就要想到这种算法思想，然后滑动窗口主要分为四个步骤，进窗口、判断、出窗口、更新结果；其中更新结果要根据不同的情况放在不同的位置，比如上面这道题
  
  这里使用滑动窗口算法，用于找到数组中和大于等于目标值 target 的最短子数组的长度。
  1. 初始化：使用两个指针 left 和 right，都初始指向数组的起始位置。同时定义变量 sum 用来记录当前窗口中元素的和，以及变量 len 用来记录当前找到的最短子数组的长度。
  2. 窗口扩展：在一个循环中，不断将右指针 right 向右移动，累加元素的值到 sum 中。如果 sum 大于等于目标值 target，说明当前窗口的和满足条件。
  3. 窗口收缩：进入内层循环，将左指针 left 向右移动，缩小窗口大小，同时更新 len 为当前窗口的长度。然后从 sum 中减去左侧移出窗口的元素的值。
  4. 循环继续：继续上述步骤，直到右指针 right 移动到数组的末尾。在整个过程中，不断更新 len 为找到的最短子数组的长度。
  5. 返回结果：最终返回 len，如果没有找到满足条件的子数组，返回 0。
  代码
```
class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        int n=nums.size(),sum=0,len=INT_MAX;
        for(int left=0,right=0;right
            sum+=nums[right];
            while(sum=target){
                len=min(len,right-left+1);
                sum-=nums[left++];
            }
        }
        return len==INT_MAX?0:len;
    }
};
```
  02.无重复字符的最长子串
  
  题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/
  
  给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
  
  示例 1:
```
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
```
  示例 2:
```
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
```
  示例 3:
```
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
```
  思路
  
  这里使用暴力枚举的方法是可以通过的，但是不推荐，这里我们使用滑动窗口来进行遍历，再借用一个哈希数组来记录字符出现的频次，每个字符最多出现一次，如果出现两次，那么左边一直向右滑动，直到变为1，再进行滑动时，我们更新最大长度，在使用哈希存储时，因为这里是字符，我们可以使用数组模拟哈希结构，这样可以提高效率。
  1. 初始化：使用两个指针 left 和 right 分别指向字符串的起始位置，并初始化一个长度为 128 的哈希表 hash 用于记录字符出现的次数。同时，初始化变量 len 用于记录当前的最长无重复字符子串的长度。
  2. 窗口扩展：在一个循环中，不断将右指针 right 向右移动，同时在哈希表中记录字符的出现次数。如果发现当前字符的出现次数大于 1，说明出现了重复字符。
  3. 窗口收缩：进入内层循环，将左指针 left 向右移动，缩小窗口大小。在这个过程中，不断减少哈希表中左指针对应字符的出现次数，直到当前窗口中没有重复字符为止。
  4. 更新最长长度：在每一步中，都更新 len 为当前窗口的长度 right - left + 1 与已经记录的最大长度的较大者。
  5. 循环继续：继续上述步骤，直到右指针 right 移动到字符串的末尾。
  6. 返回结果：最终返回 len，即最长无重复字符子串的长度。
  代码
```
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128]={0};
        int n=s.size(),len=0,left=0,right=0;
        while(right
            hash[s[right]]++;
            while(hash[s[right]]1) hash[s[left++]]--;
            len = max(len,right-left+1);
            right++;
        }
        return len;
    }
};
```
  03.最大连续1的个数 III
  
  题目链接：https://leetcode.cn/problems/max-consecutive-ones-iii/
  
  给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
  
  示例 1：
```
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
```
  示例 2：
```
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
```
  思路
  
  这里我们首先不要被题目误导，题目让我们翻转0，我们也不用真的翻转，我们可以利用滑动窗口的思想，在窗口内最大容纳k个0，超过就出窗口，直到又是k个0，再继续入窗口，每次更新最大长度即可。
  1. 初始化：使用两个指针 left 和 right 分别指向数组的起始位置，并初始化变量 zero 用于记录当前窗口中 0 的个数。同时，初始化变量 len 用于记录当前的最大长度。
  2. 窗口扩展：在一个循环中，不断将右指针 right 向右移动。如果当前元素为 0，将 zero 增加 1。
  3. 窗口收缩：进入内层循环，如果窗口中的 0 的个数大于 k，说明需要缩小窗口，将左指针 left 向右移动，减少窗口中 0 的个数。在这个过程中，如果左指针指向的元素是 0，则将 zero 减少 1。
  4. 更新最大长度：在每一步中，都更新 len 为当前窗口的长度 right - left + 1 与已经记录的最大长度的较大者。
  5. 循环继续：继续上述步骤，直到右指针 right 移动到数组的末尾。
  6. 返回结果：最终返回 len，即包含最多 k 个 0 的连续子数组的最大长度。
  代码
```
class Solution {
public:
    int longestOnes(vector& nums, int k) {
        int n=nums.size(),zero=0,len=0;
        for(int left=0,right=0;right
            if(nums[right]==0) zero++;
            while(zerok) 
                if(nums[left++]==0) zero--;
            len=max(len,right-left+1);
        }
        return len;
    }
};
```
  04.将 x 减到 0 的最小操作数
  
  题目链接：https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
  
  给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。
  
  如果可以将 x 恰好减到 0 ，返回最小操作数；否则，返回 -1 。
  
  示例 1：
```
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
```
  示例 2：
```
输入：nums = [5,6,7,8,9], x = 4
输出：-1
```
  示例 3：
```
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
```
  思路
  
  首先我们看到这道题，可能并不容易想到用滑动窗口来解，可能有很多人开始会想到双指针，但是，那样要处理的细节太多，不容易通过，其实这里我们可以将问题转化，从左右两边减去最少的操作数来达到要求，我们可以转换成将数组总和减去X，在中间找到最长的子数组之和等于这个数，再将原数组长度与子数组长度相减便可以求出最小操作数，这样是不是就更简单了呢？
  1. 计算总和：遍历数组，计算数组中所有元素的和，并保存在变量 sum 中。
  2. 计算目标差值：计算目标差值 t，即 t = sum - x。
  3. 滑动窗口求解：使用滑动窗口的思想，在一个循环中，不断将右指针 right 向右移动，累加元素的值到 tmp 中。同时，在内层循环中，如果 tmp 大于目标差值 t，将左指针 left 向右移动，减少窗口的和。在每一步中，检查当前窗口的和是否等于目标差值 t。
  4. 更新最大窗口长度：在每一步中，如果当前窗口的和等于目标差值 t，则更新 ret 为当前窗口的长度 right - left + 1 和已经记录的最大长度的较大者。
  5. 计算结果：最终返回操作数，即数组长度减去最大窗口长度。如果 ret 仍然为初始值 -1，则说明无法找到符合条件的子数组，返回 -1。
  代码
```
class Solution {
public:
    int minOperations(vector& nums, int x) {
        int n=nums.size(),sum=0,ret=-1;
        for(const auto& num : nums) sum+=num;
        int t=sum-x;
        if(t
            tmp+=nums[right];
            while(tmpt) tmp-=nums[left++];
            if(tmp==t) ret=max(ret,right-left+1);
        }
        if(ret==-1) return -1;
        else return n-ret;
    }
};

public:
    int totalFruit(vector
        int hash[100001]={0};
        int ret=0,kind=0,n=fruits.size();
        for(int left=0,right=0;right
            if(hash[fruits[right]]==0) kind++;
            hash[fruits[right]]++;
            if(kind2){
                hash[fruits[left]]--;
                if(hash[fruits[left]]==0) kind--;
                left++;
            }
            ret=max(ret,right-left+1);
        }
        return ret;
    }
};

public:
    vector
        vector0};
        int hash2[26]={0};
        for(const auto& c:p) hash1[c-'a']++;
        int n=s.size(),m=p.size(),count=0;
        for(int left=0,right=0;right
            char c1=s[right];
            if(++hash2[c1-'a']
                char c2=s[left++];
                if(hash2[c2-'a']--
public:
    vector
        vector
            unordered_map
                string str1=s.substr(right,len);
                hash2[str1]++;;
                if(hash1.count(str1)&&hash2[str1]
                    string str2=s.substr(left,len);
                    if(hash1.count(str2)&&hash2[str2]
public:
    string minWindow(string s, string t) {
        int hash1[128]={0};
        int hash2[128]={0};
        int kind=0;
        for(const auto& ch:t) 
            if(hash1[ch]++==0) kind++;
        
        int begin=-1,minl=INT_MAX,n=s.size();
        for(int left=0,right=0,count=0;right
            char c1=s[right];
            if(++hash2[c1]==hash1[c1]) count++;
            while(count==kind){
                if(right-left+1
                    minl=right-left+1;
                    begin=left;
                }
                char c2=s[left++];
                if(hash2[c2]--==hash1[c2]) count--;
            }
        }
        if(begin==-1) return "";
        return s.substr(begin,minl);
    }
};
```

算法沉淀——滑动窗口（leetcode真题剖析）

算法沉淀——滑动窗口

01.长度最小的子数组

02.无重复字符的最长子串

03.最大连续1的个数 III

04.将 x 减到 0 的最小操作数

php redis分布式锁

linux内存缓存占用过高分析和优化

stm32编写Modbus步骤

如何保证数据库和缓存的一致性

Mongodb聚合操作中的$unset

私域引流宝PHP源码以及搭建教程

算法沉淀——滑动窗口

01.长度最小的子数组

02.无重复字符的最长子串

03.最大连续1的个数 III

04.将 x 减到 0 的最小操作数

猜你喜欢

php redis分布式锁

linux内存缓存占用过高分析和优化

stm32编写Modbus步骤

如何保证数据库和缓存的一致性

Mongodb聚合操作中的$unset

私域引流宝PHP源码 以及搭建教程

私域引流宝PHP源码以及搭建教程