leetcode-209-长度最小的子数组

2021-07-02 05:05

阅读：536

标签：BMI max 复杂 tar 输出 pre 示例 int start 题目

题目描述：

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

要完成的函数：

int minSubArrayLen(int s, vector& nums)

说明：

1、这道题给定一个正整数s，和一个包含正整数的vector，要求在vector中找到最短长度的连续子数组，这个子数组中所有数的和>=s，返回子数组的长度。

2、这道题不会很难，我们用滑窗的方法找到和>=s的子数组，接着不断更新最短的长度，最终返回这个最短的长度即可。

最后要考虑一下边界情况，也就是当滑窗到达vector末尾了怎么处理，和vector中没有元素的情况。

代码如下：（附详解）

    int minSubArrayLen(int s, vector& nums) 
    {
        if(nums.empty())return 0;//vector中没有元素，找不到满足条件的子数组，返回0
        int start=0,end=0,s1=nums.size(),sum=nums[0],record=INT_MAX;//start表示滑窗的开端，end表示滑窗末端
        while(start

上述代码实测8ms，beats 98.44% of cpp submissions。

leetcode-209-长度最小的子数组

标签：BMI max 复杂 tar 输出 pre 示例 int start 题目

原文地址：https://www.cnblogs.com/king-3/p/9634081.html

上一篇：算法系列教程01 - 开篇

下一篇：springboot 中使用thymeleaf

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：leetcode-209-长度最小的子数组
文章链接：http://soscw.com/essay/100641.html

亲，登录后才可以留言！

leetcode-209-长度最小的子数组

题目描述：

要完成的函数：

说明：

评论

热门文章

推荐文章

最新文章

置顶文章