每日一题: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)的时间复杂度,理解滑动窗口的本质才有助于你解决类似问题不会毫无思路。

相关文章
|
8天前
|
人工智能
力扣100114. 元素和最小的山形三元组 II(中等)
力扣100114. 元素和最小的山形三元组 II(中等)
|
14天前
滑动窗口最大值(leetcode hot100)
滑动窗口最大值(leetcode hot100)
|
14天前
|
索引
LeetCode438题(无敌双指针——滑动窗口)
LeetCode438题(无敌双指针——滑动窗口)
|
14天前
|
索引
leetcode代码记录(最长重复子数组
leetcode代码记录(最长重复子数组
15 0
|
14天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
16 0
|
14天前
leetcode代码记录(滑动窗口最大值
leetcode代码记录(滑动窗口最大值
13 0
|
14天前
leetcode代码记录(长度最小的子数组
leetcode代码记录(长度最小的子数组
16 0
|
14天前
【力扣】209. 长度最小的子数组
【力扣】209. 长度最小的子数组
|
2天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
10 0
|
2天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
8 0