# 862. Shortest Subarray with Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of `A` with sum at least `K`.

If there is no non-empty subarray with sum at least `K`, return `-1`.

Example 1:

``````Input: A = [1], K = 1
Output: 1
``````

Example 2:

``````Input: A = [1,2], K = 4
Output: -1
``````

Example 3:

``````Input: A = [2,-1,2], K = 3
Output: 3
``````

Note:

1. `1 <= A.length <= 50000`
2. `-10 ^ 5 <= A[i] <= 10 ^ 5`
3. `1 <= K <= 10 ^ 9`

``````class Solution {
public:
int shortestSubarray(vector<int>& A, int K) {
int n = A.size(), res = INT_MAX, sum = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = 0; i < n; ++i) {
sum += A[i];
if (sum >= K) res = min(res, i + 1);
while (!pq.empty() && sum - pq.top().first >= K) {
res = min(res, i - pq.top().second);
pq.pop();
}
pq.push({sum, i});
}
return res == INT_MAX ? -1 : res;
}
};
``````

``````class Solution {
public:
int shortestSubarray(vector<int>& A, int K) {
int n = A.size(), res = INT_MAX;
map<int, int> sumMap;
vector<int> sums(n + 1);
for (int i = 1; i <= n; ++i) sums[i] = sums[i - 1] + A[i - 1];
for (int i = 0; i <= n; ++i) {
auto pos = sumMap.upper_bound(sums[i] - K);
for (auto it = sumMap.begin(); it != pos; ++it) {
res = min(res, i - it->second);
}
sumMap.erase(sumMap.begin(), pos);
sumMap[sums[i]] = i;
}
return res == INT_MAX ? -1 : res;
}
};
``````

``````class Solution {
public:
int shortestSubarray(vector<int>& A, int K) {
int n = A.size(), res = INT_MAX;
deque<int> dq;
vector<int> sums(n + 1);
for (int i = 1; i <= n; ++i) sums[i] = sums[i - 1] + A[i - 1];
for (int i = 0; i <= n; ++i) {
while (!dq.empty() && sums[i] - sums[dq.front()] >= K) {
res = min(res, i - dq.front());
dq.pop_front();
}
while (!dq.empty() && sums[i] <= sums[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
}
return res == INT_MAX ? -1 : res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/862

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C%2B%2BJavaPython-O(N)-Using-Deque

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143768/C%2B%2B-solution-by-using-priority_queue

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/153515/c%2B%2B-upper_bound-%2B-prefix-sum-easy-to-remember-and-impl-in-10mins

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation