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.
题意:
求一个给定数组的部分连续和Sum,要求Sum大于给定数值S。返回满足条件的连续和Sum中长度最短的。
思路:
通过标记起始位置(p)、终止位置(q)构建一个滑动“窗口”,使“窗口”内元素的和Sum始终保持小于s。若从(q)端新加元素使得Sum >= s,则更新Sum的最小长度值_min,并从(p)端删除元素,保持Sum < s。
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) { const int len = nums.size(); if(len == )
return ; //初始化,_min初始化为len+1(上界)
int p = , q = , sum = , _min = len + ; for(; q < nums.size(); q++)
{
//顺序扫描数组,从q端添加元素
sum += nums[q]; //保持“窗口”值小于s
while(sum >= s)
{
if((q - p) < _min)
_min = q - p; //从p端删除元素
sum -= nums[p++];
}
} return _min > len ? : _min + ;
}
};