博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Minimum Size Subarray Sum -- leetcode
阅读量:5871 次
发布时间:2019-06-19

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

题目描写叙述:

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,

the subarray [4,3] has the minimal length under the problem constraint.

意思是讲给定一组整数数组nums和一个数字s。求的nums数组中最短长度的连续数字和,使得该和大于等于s。

比方上面实例数组 2 。3。1,2,4,3这一个数组中,大于等于7的最短连续为 3 ,4 那么 minimal为2

解题思路

定义一个start 。表示序列的事实上点,初始值为0

定义一个tempresult,用来累积连续序列和,初始值为0
定义一个minlength,用来表示最短序列。初始值为INT-MAX

  • 一个循环,首先从数组開始处i=0,此时start=0,往后累积和,tempresult+=nums[i]

  • 推断累积和和s的大小,假设大于等于s,则进行例如以下操作

    - 先计算当前minlength=min(minlength,i-satrt+1)-然后将tempresult的值减去这个序列的nums[start]。起始点start++再次计算minlength(缩短整个序列),然后继续推断该值跟s的大小,直到减去的值使得tempresult的值小于s
  • 假设小于s。则继续累积和。直到满足和大于等于s

  • 注意。还有可能存在不存在序列的,就是整个序列和都相加都小于s。这是就须要推断(程序返回时候i-start==nums.size()&&tempresult小于s

拿上面的数组列子进行解说nums= 2 ,3,1,2,4。3,s=7

首先 从2開始加,一直加到 2,3。1。2此时tempresult=8,大于等于7,先求的但当前minlength=4。然后缩短序列 start++,序列为3。1,2。对应的tempresult=6,小于7。则继续往后面累积和,3,1,2,4,然后缩短序列,变成,1,2,4,start++,此时minlength=3。然后继续缩短,2。4小于7,然后往后面继续累加,2,4,3,大于7,缩短,4,3,大于等于7,minlength=2。,到最后了。结束。

代码例如以下

class Solution {public:    int minSubArrayLen(int s, vector
& nums) { int i,start,minlength,tempresult; minlength=INT_MAX; start=0; tempresult=0; for(i=start;i
=s) { minlength=min(minlength,i-start+1); tempresult-=nums[start]; start++; while(tempresult>=s) { minlength=min(minlength,i-start+1); tempresult-=nums[start]; start++; } } } if(i-start==nums.size()&&tempresult

转载地址:http://hdxnx.baihongyu.com/

你可能感兴趣的文章
设计模式学习专栏七--------外观模式
查看>>
上海招聘职位信息
查看>>
3-25 周末总结
查看>>
学习vue笔记
查看>>
IDE顺手设置
查看>>
记一次翻译站经历
查看>>
JavaWeb项目中没有错,但是项目上面显示一个红叉的解决办法
查看>>
JavaScript 复习之语法专题
查看>>
重学Android——基于Android9.0的Activity启动流程
查看>>
前端必备技能-Charles for mac 安装和配置
查看>>
关于一天内时针分针重合次数
查看>>
数组 JSON字符串 数组过程中的问题
查看>>
各平台安装使用 MTR 诊断网络
查看>>
Flutter 支持图片以及特殊文字的输入框(一)使用方法
查看>>
武汉区块链软件公司:区块链将改动游戏工业的五种方法
查看>>
Ubuntu 16 04 LTS 完美安装QQ
查看>>
精彩展览这么多 我要去博物馆看看
查看>>
一致性模型之Sequential Consistency
查看>>
java 设计模式
查看>>
OAuth2.0
查看>>