209. Minimum Size Subarray Sum

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;
    }
};
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容