每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)

简介: 每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)

每日一题系列(day 11)

前言:

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,拾取经验,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️


题目:

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

示例:

  提示:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

解法一:

  思路:

  根据示例我们可以了解到,这题是让我们求一个最短的子数组,并且保证这个子数组元素的和要>= target值的。

  我们可以使用两个指针当做数组的左右区间,用left,right指针指向数组的下标,left表示左区间,right表示右区间,用sum值计算每次移动区间之后区间元素值的和,最后遍历完返回最小区间数组。

  O(n^3)的时间复杂度还是太大了,我们还能不能再暴力的基础上再优化呢?,其实我们仔细观察,那个求和的O(n)似乎还有优化的空间。
  在right移动的时候我们可以记录下来每一次计算的sum值,right向后移动一位我们只需要在前面sum的基础上加上right下一位的值即可,同理,当left向后移动一位的时候,我们只需要在sum的基础上减去left移动之前的值。
  除此之外,我们其实当sum的值大于等于target值的时候right就可以不用再向后移动了,因为这个时候你的区间值的和已经大于了target值,right往后遍历只会让区间增大,所以没有遍历的必要了,直接开启下一轮的循环。left++

  当区间的sum值要大于等于target的值的时候,我们就需要更新区间ans的值了,如果本次区间的ans要小于之前记录的最小区间,则将区间更新为本次区间大小,表示到目前为止,最小符合条件的区间为当前区间。这样遍历到最后,我们就能得到符合条件的最小区间了。

  这样我们暴力枚举的时间复杂度就降为O(n^2)了。

  代码实现:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();//nums数组长度
        if(n == 0) return 0;
        int ans = INT_MAX;//长度设置为整形的最大值,防止误判
        for(int i = 0 ; i < n ; i++)
        {
            int sum = 0;
            for(int j = i ; j < n ; j++)//i,j就是左右指针
            {
                sum += nums[j];//sum进行累加
                if(sum >= target)
                {
                    ans = min(ans, j - i + 1);//保留较小的区间
                    break;//终结本次循环
                }
            }
        }
        return ans == INT_MAX ? 0 : ans;//防止误判
    }
};

  可以看到我们的测试用例过了,但是我们的执行结果却超时了,这说明我们的时间复杂度就太高了,我们应该想一想其他的方法来降低时间复杂度,这就是我接下来要说的————滑动窗口


解法二:

  思路:

  其实整体思路和上面差不多,不过滑动窗口的left和right都是在向右移动,right指针没有回退的操作,这种“同向双指针” ,也被称为滑动窗口,其实很形象,左右指针一直同向移动,看起来就像是在滑动的窗口,故此得名。

  我们可以看到,如果是最坏的情况,也就是左右指针把数组都遍历一遍,也就是O(2n)时间复杂度,也就是 O(N) 级别的时间复杂度,空间上只用了几个变量,所以 空间复杂度为O(1),相比较之下,我们的滑动窗口确实非常好用。

  代码实现:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        int n = nums.size();
        int len = INT_MAX, sum = 0;
        while(right < n)
        {
            sum += nums[right];
            while(sum >= target)
            {
                len = min(len, right - left + 1);//比较找出最小区间
                sum -= nums[left++];
            }
            right++;
        }
        return len == INT_MAX ? 0 : len;
    }
};

  今天是第一次写滑动窗口的题,果然非常奇妙,居然只有O(N)的时间复杂度,理解滑动窗口的本质才有助于你解决类似问题不会毫无思路。

相关文章
|
2月前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
33 1
|
2月前
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
19 0
|
4月前
|
算法 Python
【Leetcode刷题Python】子数组查找
一个用于寻找给定字符串中最长重复子串的Python函数实现,采用了滑动窗口的方法来检测重复的子串。
21 1
|
4月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
43 0
|
4月前
|
存储 Python
【Leetcode刷题Python】239. 滑动窗口最大值
文章介绍了两种解决LeetCode上"滑动窗口最大值"问题的方法:使用大堆树和双向递减队列,提供了详细的解析和Python代码实现。
37 0
|
6月前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
34 1
|
6月前
|
算法 测试技术 程序员
力扣经典150题第三十题:长度最小的子数组
力扣经典150题第三十题:长度最小的子数组
30 1
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
47 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行