博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode-209-长度最小的子数组
阅读量:5842 次
发布时间:2019-06-18

本文共 788 字,大约阅读时间需要 2 分钟。

题目描述:

给定一个含有 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
& 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。

转载于:https://www.cnblogs.com/chenjx85/p/9634081.html

你可能感兴趣的文章
金庸笔下的爱情故事
查看>>
Cookie跨域操作
查看>>
GC中的对象自救
查看>>
(Mirage系列之十一)终端初始化
查看>>
(App Volumes 系列一) AppVolumes基本介绍
查看>>
马的种类 (二)
查看>>
Linux YUM之将光盘作为YUM源
查看>>
清除图片缓存
查看>>
Exchange server 2013(十四)WSUS部署及组策略设置(1)
查看>>
Windows 2008 R2 DFS分布式文件系统配置
查看>>
用 zxing生成二维码图片
查看>>
centos: 客户端修改git ssh连接密码
查看>>
Cobbler-自动化部署神器
查看>>
幸运中奖
查看>>
在CentOS 6.0 (Final) 安装oracle11gR2
查看>>
我的友情链接
查看>>
JAVA容器
查看>>
《JAVA编程思想》学习笔记——第十六章 数组
查看>>
ubuntu ufw设置
查看>>
用nodejs实现json和jsonp服务
查看>>