Lintcode406 Minimum Size Subarray Sum solution 题解
发布在刷题能手——Lintcode 题解2018年4月16日view:243
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

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 -1 instead.

给定一个由 n 个正整数组成的数组和一个正整数 s ,请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解,则返回 -1。

【题目链接】

www.lintcode.com/en/problem/minimum-size-subarray-sum/

【题目解析】

sum为前i个数的和,长度比nums多一个,sum[0] = 0。这样从0开始一直到len,遍历sum计算sum[j]与sum[i]的差大于等于s的时候的j-i长度,把它与minlen比较,如果比minlen小就更新minlen。

一开始minlen的初始化值是len + 1,如果最后minlen的值仍旧为len + 1,说明没有找到这样的minlen满足题意。则直接返回0;否则返回minlen的值

【参考答案】

www.jiuzhang.com/solutions/minimum-size-subarray-sum/

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏