一、题目

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1
Output: 1
Example 2:

Input: nums = [1,2], k = 4
Output: -1
Example 3:

Input: nums = [2,-1,2], k = 3
Output: 3

Constraints:

1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109

二、题解

class Solution {
public:int shortestSubarray(vector<int>& nums, int k) {int n = nums.size();deque<int> q;int res = INT_MAX;vector<long long> sum(n+1,0);for(int i = 0;i < n;i++){sum[i+1] = sum[i] + nums[i];}for(int r = 0;r <= n;r++){while(!q.empty() && sum[r] - sum[q.front()] >= k){res = min(res,r - q.front());q.pop_front();}while(!q.empty() && sum[q.back()] >= sum[r]) q.pop_back();q.push_back(r);}return res == INT_MAX ? -1 : res;}
};