1. 題目

返回 A 的最短的非空連續(xù)子數(shù)組的長度，該子數(shù)組的和至少為 K 。

如果沒有和至少為 K 的非空子數(shù)組，返回 -1 。

示例 1： 輸入：A = [1], K = 1 輸出：1示例 2： 輸入：A = [1,2], K = 4 輸出：-1示例 3： 輸入：A = [2,-1,2], K = 3 輸出：3提示： 1 <= A.length <= 50000 -10 ^ 5 <= A[i] <= 10 ^ 5 1 <= K <= 10 ^ 9

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：
LeetCode 560. 和為K的子數(shù)組（前綴和差分）
LeetCode 523. 連續(xù)的子數(shù)組和（求余 哈希）
LeetCode 974. 和可被 K 整除的子數(shù)組（哈希map）

• 參考官方思路
• deque存儲前綴和的下標(biāo)，隊內(nèi)前綴和需要嚴(yán)格單調(diào)遞增
• 跟隊首的差值 >= k 時，記錄最小長度，刪除隊首
  

class Solution { public:int shortestSubarray(vector<int>& A, int K) {vector<int> presum(A.size()+1,0);int i, minLen = INT_MAX, sum = 0;deque<int> q;//存儲下標(biāo)，按照隊內(nèi)presum升序q.push_back(0);//邊界條件，前綴和為0，下標(biāo)為0for(i = 0; i < A.size(); ++i){presum[i+1] = presum[i] + A[i];//前綴和while(!q.empty() && presum[q.back()] >= presum[i+1])q.pop_back();while(!q.empty() && (presum[i+1]-presum[q.front()] >= K)){minLen = min(minLen, i+1-q.front());q.pop_front();}q.push_back(i+1);}if(minLen == INT_MAX)return -1;return minLen;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 862. 和至少为 K 的最短子数组（前缀和+deque单调栈）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。