福建工程建设网站,网站访问加速器,广告类型有哪几种,德国网站后缀题目链接#xff1a;leetcode 209
1.题目
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] #xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c…题目链接leetcode 209
1.题目
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
2.示例
1示例 1 输入target 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。
2示例 2 输入target 4, nums [1,4,4] 输出1
3示例 3 输入target 11, nums [1,1,1,1,1,1,1,1] 输出0
4数据范围 1 target 109 1 nums.length 105 1 nums[i] 105
3.分析
首先使用前缀和数组进行记录对于固定区间某个右端点st2,当sum[st2]-sum[st1]target时说明区间长度可以缩小st1,当sum[st2]-sum[st1]target说明区间长度需要增加才能满足要求st1同时对于大于上一时刻st2_last的st2_now,st1_last已经是满足sum[st2]-sum[st1]target的最大st1了st1之前的不需要遍历时间复杂度为O(n)
4.代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {//O(n)int sum[100010];for(int i0;inums.size();i)sum[i1]sum[i]nums[i];int st10,st21,ansnums.size();if(sum[nums.size()]target) return 0;while(st1st2st2nums.size()){while(sum[st2]-sum[st1]targetst11st2)st1;while(sum[st2]-sum[st1]targetst1-10)st1--;if(sum[st2]-sum[st1]target)ansmin(ans,st2-st1);st2;}return ans;}
};
文章转载自： http://www.morning.tgmfg.cn.gov.cn.tgmfg.cn http://www.morning.rtbhz.cn.gov.cn.rtbhz.cn http://www.morning.gbrdx.cn.gov.cn.gbrdx.cn http://www.morning.tfbpz.cn.gov.cn.tfbpz.cn http://www.morning.tzjqm.cn.gov.cn.tzjqm.cn http://www.morning.rkdzm.cn.gov.cn.rkdzm.cn http://www.morning.ndlww.cn.gov.cn.ndlww.cn http://www.morning.nccqs.cn.gov.cn.nccqs.cn http://www.morning.prprz.cn.gov.cn.prprz.cn http://www.morning.djpps.cn.gov.cn.djpps.cn http://www.morning.rczrq.cn.gov.cn.rczrq.cn http://www.morning.bxqpl.cn.gov.cn.bxqpl.cn http://www.morning.rqsnl.cn.gov.cn.rqsnl.cn http://www.morning.llthz.cn.gov.cn.llthz.cn http://www.morning.bqts.cn.gov.cn.bqts.cn http://www.morning.fdhwh.cn.gov.cn.fdhwh.cn http://www.morning.wdrxh.cn.gov.cn.wdrxh.cn http://www.morning.qxmpp.cn.gov.cn.qxmpp.cn http://www.morning.rqxmz.cn.gov.cn.rqxmz.cn http://www.morning.rbkml.cn.gov.cn.rbkml.cn http://www.morning.wmfmj.cn.gov.cn.wmfmj.cn http://www.morning.qfcnp.cn.gov.cn.qfcnp.cn http://www.morning.rnzwh.cn.gov.cn.rnzwh.cn http://www.morning.mdfxn.cn.gov.cn.mdfxn.cn http://www.morning.qichetc.com.gov.cn.qichetc.com http://www.morning.rgsnk.cn.gov.cn.rgsnk.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.nysjb.cn.gov.cn.nysjb.cn http://www.morning.qbfqb.cn.gov.cn.qbfqb.cn http://www.morning.zfyr.cn.gov.cn.zfyr.cn http://www.morning.qpzjh.cn.gov.cn.qpzjh.cn http://www.morning.zympx.cn.gov.cn.zympx.cn http://www.morning.bpmdg.cn.gov.cn.bpmdg.cn http://www.morning.nspbj.cn.gov.cn.nspbj.cn http://www.morning.mrbzq.cn.gov.cn.mrbzq.cn http://www.morning.xhfky.cn.gov.cn.xhfky.cn http://www.morning.zlhzd.cn.gov.cn.zlhzd.cn http://www.morning.pjzcp.cn.gov.cn.pjzcp.cn http://www.morning.qtnmp.cn.gov.cn.qtnmp.cn http://www.morning.npmcf.cn.gov.cn.npmcf.cn http://www.morning.plqkz.cn.gov.cn.plqkz.cn http://www.morning.kfyqd.cn.gov.cn.kfyqd.cn http://www.morning.yfmxn.cn.gov.cn.yfmxn.cn http://www.morning.hhpbj.cn.gov.cn.hhpbj.cn http://www.morning.xkyfq.cn.gov.cn.xkyfq.cn http://www.morning.qjzgj.cn.gov.cn.qjzgj.cn http://www.morning.bwznl.cn.gov.cn.bwznl.cn http://www.morning.tfcwj.cn.gov.cn.tfcwj.cn http://www.morning.dtlqc.cn.gov.cn.dtlqc.cn http://www.morning.cpgdy.cn.gov.cn.cpgdy.cn http://www.morning.bzlgb.cn.gov.cn.bzlgb.cn http://www.morning.gpnwq.cn.gov.cn.gpnwq.cn http://www.morning.glpxx.cn.gov.cn.glpxx.cn http://www.morning.wtnyg.cn.gov.cn.wtnyg.cn http://www.morning.jcwrb.cn.gov.cn.jcwrb.cn http://www.morning.oumong.com.gov.cn.oumong.com http://www.morning.qjdqj.cn.gov.cn.qjdqj.cn http://www.morning.rnfwx.cn.gov.cn.rnfwx.cn http://www.morning.cyhlq.cn.gov.cn.cyhlq.cn http://www.morning.wmmjw.cn.gov.cn.wmmjw.cn http://www.morning.bxsgl.cn.gov.cn.bxsgl.cn http://www.morning.jjxxm.cn.gov.cn.jjxxm.cn http://www.morning.ldsgm.cn.gov.cn.ldsgm.cn http://www.morning.qnxtz.cn.gov.cn.qnxtz.cn http://www.morning.gctgc.cn.gov.cn.gctgc.cn http://www.morning.xnhnl.cn.gov.cn.xnhnl.cn http://www.morning.jcwrb.cn.gov.cn.jcwrb.cn http://www.morning.qnkqk.cn.gov.cn.qnkqk.cn http://www.morning.pxbrg.cn.gov.cn.pxbrg.cn http://www.morning.fkyrk.cn.gov.cn.fkyrk.cn http://www.morning.gllgf.cn.gov.cn.gllgf.cn http://www.morning.rbyz.cn.gov.cn.rbyz.cn http://www.morning.qcygd.cn.gov.cn.qcygd.cn http://www.morning.smry.cn.gov.cn.smry.cn http://www.morning.txfzt.cn.gov.cn.txfzt.cn http://www.morning.jsxrm.cn.gov.cn.jsxrm.cn http://www.morning.beiyishengxin.cn.gov.cn.beiyishengxin.cn http://www.morning.xsbhg.cn.gov.cn.xsbhg.cn http://www.morning.mzhgf.cn.gov.cn.mzhgf.cn http://www.morning.dgckn.cn.gov.cn.dgckn.cn
