当前位置:   article > 正文

给你一个整数数组 nums 和一个整数 k ,找出 nums 中和至少为 k 的 最短非空子数组 ,并返回该子数组的长度。如果不存在这样的 子数组 ,返回 -1 。子数组 是数组中 连续 的一部分_给定一个长度为n的整数数组nums和一个正整数k

给定一个长度为n的整数数组nums和一个正整数k

class Solution {

public:

    int shortestSubarray(vector<int>& nums, int k) {

        int n = nums.size();

        vector<long> preSumArr(n + 1);

        for (int i = 0; i < n; i++) {

            preSumArr[i + 1] = preSumArr[i] + nums[i];

        }

        int res = n + 1;

        deque<int> qu;

        for (int i = 0; i <= n; i++) {

            long curSum = preSumArr[i];

            while (!qu.empty() && curSum - preSumArr[qu.front()] >= k) {

                res = min(res, i - qu.front());

                qu.pop_front();

            }

            while (!qu.empty() && preSumArr[qu.back()] >= curSum) {

                qu.pop_back();

            }

            qu.push_back(i);

        }

        return res < n + 1 ? res : -1;

    }

};

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/765961
推荐阅读
相关标签
  

闽ICP备14008679号