滑动窗口经典入门题-——长度最小子数组

本文主要是介绍滑动窗口经典入门题-——长度最小子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法原理

滑动窗口是一种在序列（例如数组或链表）上解决问题的算法模式。它通常用于解决子数组或子字符串的问题，其中滑动窗口表示一个范围，这个范围在序列上移动，以便找到满足特定条件的子数组或子字符串。

算法的基本思想是维护两个指针，通常是左右两个指针，表示滑动窗口的左右边界。通过调整这两个指针，可以滑动窗口在序列上移动。在每个窗口位置，都可以根据问题的要求进行处理，比如计算窗口内的和、最大值、最小值，或者检测满足某些条件的子数组或子字符串等。

滑动窗口算法的一般步骤如下：

初始化左右指针： 将左指针和右指针初始化为序列的起始位置。

滑动窗口： 移动右指针以扩大窗口，或移动左指针以缩小窗口，直到满足问题的条件。

处理窗口数据： 在每个窗口位置，根据问题的要求处理窗口内的数据，比如计算窗口内的和、最大值、最小值，或者检测满足某些条件的子数组或子字符串。

更新结果： 根据问题的要求更新结果。

重复： 重复2-4步骤，直到右指针到达序列的末尾。

滑动窗口算法通常能够在线性时间内解决一些与子数组或子字符串相关的问题，因为每个元素至多被访问两次（一次由左指针，一次由右指针）。这种算法的时间复杂度通常是 O(N)，其中 N 是序列的长度。

实际应用中，滑动窗口算法可以解决一系列问题，如最大子数组和、最小覆盖子串、最长无重复字符子串等。

题目解析

废话不多说先上题目链接leetcode—长度最小子数组
那么接下来我们一起解析一下例题如下图

首先最重要的肯定是读懂题目，题目意思其实也很容易读懂意思就是给我们一个数字target和一个数组，要求在这个数组中找到一个必须是连续的子数组并且这个子数组每个元素加起来>=target并从找到的这些数组中取一个最短的数组那么炸一看可能会感觉有些茫然，但是学习算法我们要记住一个步骤就是面对一个题目的时候先想一下如何暴力的把他求出来，那么很简单那就是找到所有的子数组并从这些子数组中找到和>=target的数组之后取得最小值那么我们把暴力的方法先写出来代码如下

暴力枚举法的代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans=0x9f9f9f;for(int i=0;i<nums.size();i++){int t=0;for(int j=i;j<nums.size();j++){t+=nums[j];if(i==j){if(t>=target){ans=min(ans,j-i+1);break;}}if(t>=target){ans=min(ans,j-i+1);break;}}}if(ans==0x9f9f9f){return 0;}return ans;}
};

由于力扣的后台测试数据比较小所以这个暴力的解法也可以过但是我们可以清楚的看到这个算法的时间复杂度达到了O(n^2)因此这个时间负责度还是比较高的因此我们有没有更简单的办法呢？

优化

使用滑动窗口进行优化，
在这道题目中我们可以看到两个重要信息

1、子数组必须是连续的
2、子数组的和需要>=target

那么我们可以想一下我们可以使用两个指针一个是left一个是right当left和right之间的元素和小于target的时候就让right一直向右移动，当right和left之间的元素大于等于target的时候我们更新一下此时的长度是否为最短，然后再让left左移查看此时right和left的元素之和是否大于等于target如果是就继续上一步操作即继续更新我们的最短长度，一直到right和left之间的数据小于target为止之后再让right指针右移即可。
我给大家举出一个例子说明一下。

第一步初始化

第二步right右移

此时我们可以发现right和left之间的元素和超过了target因此我们与目标值进行比较取得较小的那个然后让left右移之后再进行查看此时right和left之间的元素和是否大于等于target。

第三步left右移

此时我们右移后发现right和left之间的元素和小于target因此right继续右移然后后续一直重复这个操作即可

滑动窗口法的代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0;int right=0;int sum=nums[0];int ansmin=100010;while(right<nums.size()&&left<nums.size()){if(sum>=target){ansmin=min(right-left+1,ansmin);sum-=nums[left];left++;}else{right++;if(right<nums.size())sum+=nums[right];else break;}}if(ansmin==100010){return 0;}return ansmin;}
};

我们可以从用时分布图清楚的看到我们的时间效率有了很大的提升。

这篇关于滑动窗口经典入门题-——长度最小子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---