Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous 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.
求已知数组里,元素加起来大于等于给定的数的最小连续子数组的长度。
我的想法是,建一个队列。遍历数组,每次往队列里加入一个数,如果超过给定的数s,就把队列前头的数去掉,使他刚好大于等于s且最短,这个队列就是那个Subarray ,遍历过程记录最小值。
代码如下:
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
queue<int> q;
if(s < 0)
return -1;
int sum = 0;
int res = INT_MAX;
for (int i = 0; i < nums.size(); i++)
{
int r = enqueue(nums[i], s, sum, q);
if (r < res && r != -1)
res = r;
}
if(res == INT_MAX)
res = 0;
return res;
}
int enqueue(int n, int s, int &sum, queue<int> &q)
{
q.push(n);//入队
sum += n;
if (sum < s)
return -1; //队列里的元素相加还不够s
while (q.empty() == false)
{
int f = q.front();
if (sum - f >= s) // 除去头部 sum还大于等于s,就头元素出队。
{
q.pop();
sum -= f;
}
else // 返回此时队列的长度 这队列就是那个子数组 返回队列长度。
{
return q.size();
}
}
return -1;
}
};
网友评论