注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex209 Minimum Size Subarray Sum  

2015-05-22 21:53:37|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
感觉这题挺难的

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.


线性算法比较好懂,就是一个窗口的滑动,如果ps到pe的值小于target,pe就继续增大,ps不变。
如果sum值大于target了之后,ps的下标左移,在这个过程中计算满足条件的最短范围,并且更新。这个算法只需要遍历一次数组,复杂度是o(N).

第二种算法就比较巧妙了,是一个o(NlogN)的算法。开始我以为要先快排,然后再进行二分查找呢~~搜了一下网上的思路,大致是这样的
先构造一个非递减的序列sum和,sum[i]表示的就是nums中0->i-1的和。接着遍历数组nums[i],在i下标的时候
从sums的  i+1到最后二分搜索sums[i]+ target的应该在的下标(二分搜索是可以做到的)。两种算法的代码如下

class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {

//sort(nums.begin(), nums.end()); //先进行排序
int ps, pe;
int i, j;
ps = 0; pe = 0;
int sum = 0;
int len = nums.size();
int result = len + 1;
while (pe < len)
{
sum += nums[pe]; //加上右边的值
while (sum >= s)
{
if ((pe - ps+1) == 1)
return 1;

//当前的长度是pe-ps +1
result = myMin(result, pe - ps + 1);
sum -= nums[ps];
ps++;//起始值下标加1
}
pe++; //这个时候sum<s了
}
if (result == (len+1))
{
return 0; //压根儿没有找到
}
else
{
return result;
}
}
int myMin(int a, int b)
{
return a>b ? b : a;
}
int minSubArrayLen1(int s, vector<int>& nums)
{
if (nums.size() <= 0)
return 0;
// 这个算法的复杂度是nlogn需要用到二分搜索
int len = nums.size();
vector<int>sums(len+1,0); //构造一个len + 1的求和数组 其中sum[i]表示 0->i-1的和
int i;
for (i = 1; i < len+1; i++)
sums[i] = (sums[i-1] + nums[i-1]);
int right, result=len+1;
for (i = 0; i < len+1; i++)
{
right = binarySearch(i+1,len,sums[i]+s,sums);
// start下标应该从 i的下一个开开始
//而key值刚好是sums[i]也就是从0到i-1,加上s开始
//举个例子 nums ={1,4,4}
//sums = {0,1,5,9} 当i =1的时候应该从sum的2下标开始搜索
//而且key的话,应该是 1 + s = 5 也就是sum[1]+s
if (right == (len + 1))
break;
result = myMin(result,right-i);
}
return result == (len + 1) ? 0:result;
}
int binarySearch(int left,int right,int key,vector<int> nums)
{
//二分搜索是可以查找到其原本可以插入的位置
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (nums[mid] >= key)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return left;
}
};


参考
这个作者写的很好
http://www.cnblogs.com/grandyang/p/4501934.html
  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017