大家好,又见面了,我是全栈君。
题目描写叙述:
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
首先 从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<int>& nums) {
int i,start,minlength,tempresult;
minlength=INT_MAX;
start=0;
tempresult=0;
for(i=start;i<nums.size();i++)
{
tempresult+=nums[i];
if(tempresult>=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<s)
return 0;
return minlength;
}
};
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115496.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...