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

题目描述:

给定一个含有 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<int>& nums) 

说明:

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

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

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

代码如下:(附详解)

    int minSubArrayLen(int s, vector<int>& 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<s1)//对开端在vector中的每个位置,都进行考虑
        {
            while(sum<s)//当和小于s时,末端不断向右走,sum也不断地加
            {
                end++;
                if(end==s1)//如果超出vector的长度,那么当前滑窗不满足条件的,这个时候也就可以返回record了
                    return record==INT_MAX?0:record;//如果record等于初始值,那么必然没有改变过record,也就是从头到尾都没找到满足条件的滑窗
                sum+=nums[end];
            }
            record=min(record,end-start+1);//更新record
            sum-=nums[start];//减去开端
            start++;//开端到了下一位
        }
        return record;
        
    }

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

【Go 语言社区】 golang 算法课程 第一季 第2节 洗牌算法

扑克牌洗牌是我们生活中比较喜欢玩的一个游戏。那么我们有没有什么办法自己设计一个扑克牌洗牌的方法呢?在运行库当中有一个随机函数rand,它可以生成0~32767之...

43970
来自专栏偏前端工程师的驿站

基础野:细说有符号整数

Breif                                本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004的...

244100
来自专栏黑泽君的专栏

java基础学习_基础语法(下)02_day06总结

============================================================================= ==...

7010
来自专栏云霄雨霁

字符串排序----键索引记数法

16700
来自专栏计算机视觉与深度学习基础

Leetcode 31 Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically...

21050
来自专栏AI派

Numpy 修炼之道 (5)—— 索引和切片

Python 中原生的数组就支持使用方括号([])进行索引和切片操作,Numpy 自然不会放过这个强大的特性。

34660
来自专栏mathor

LeetCode8. 字符串转整数 (atoi)

9820
来自专栏小二的折腾日记

LeetCode-8-String to Integer (atoi)

讲字符串转化为整型。当然过程很简单,但是需要考虑的乱七八糟的情况很多,空格和正负号之类的。提交了一百次,终于过了,但是看到别人的代码还是很气呀,还是得多写才行,...

8530
来自专栏企鹅号快讯

SQL笔记

表达式:表达式的定义非常简单 表达式可以返回一个值 表达式的类型非常广泛 它以包括各种 类型的数据如数字字符以逻辑型等其实在下列子句 如 SELECT 和 FR...

21160
来自专栏数据结构与算法

洛谷P3357 最长k可重线段集问题(费用流)

题目描述http://www.cnblogs.com/zwfymqz/p/8559566.html 给定平面 x-O-yx−O−y 上 nn 个开线段组成的集合...

41860

扫码关注云+社区

领取腾讯云代金券