前言
题目描述
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。 如果没有和至少为 K 的非空子数组，返回 -1 。
题目解析
刚看到这道题的时候，我以为我读懂了，但其实并没有…
我知道是会用到前缀和的，因为题目中有“连续子数组”,但是 我理所当然的认为是非要从头开始的连续子数组才算数，但其实不是，如果中间某一个子数组的和至少为K了，并且最短，那么肯定返回的是这个子数组的长度。
所以现在要重新审视一下这个题目：
用前缀和肯定没有毛病，举个例子吧：
A=[17,85,93,-45,-21] K=150
虽然前三项和>150但是85+93>150而且更短。
所以要转化为队列来求：
deque<int> deq；
把此问题转化为，
遍历两次前缀和数组，找到一个x和y，令presum[x]-presum[y]>=k,并且x-y最小。
当然如果用队列来求此问题，那就将前缀和数组的下标放到队列里，然后构造一个单调的队列，而且在强调单调的同时，要记录最短长度。
（1）先将前缀和数组的第一个下标0进队列。
（2）然后遍历前缀和数组，如果下一个下标对应的值比对尾大，同时这个值和队头的值的差<k，那就将这个下标入队列，因为这个时候这个下标是什么也不满足的。
（3）如果下一个下标的值没有对尾大，即小于队尾，那就将队尾出队列，来保证单调。
（4）如果下一个下标的值与对头的值>=K，那就说明现在已经存在连续前几个子数组的和至少为K了，但是不确定是不是最短的，所以要将此时的min_len记录下来min_len=min(n+1,j-deq.front());然后将队头出队，再次比较此时这个下标对应的值和队头，如果仍然满足>=K,说明又找到一个更短的子数组的和至少为K了，如果不满足了，此时就将j入队
（5）如此做下去即可。
完整代码
//题目分析：注意到题目里有“连续子数组”很容易让人联想到前缀和数组
// 注意：我在理解该题目时存在误区
#include<iostream>
#include<queue>
#include<string>
#include<vector>
using namespace std;
class Solution{
public:
int shortestSubarray(vector<int>& A,int k){
int ans=-1;
if(A.empty()) return ans;
int n=A.size();
vector<int> presum(n+1);
presum[0]=0;
for(int i=1;i<=n;i++){
presum[i]=presum[i-1]+A[i-1];
}
int min_len=n+1;
//维护一个关于前缀和数组的单调队列
deque<int> deq;
for(int j=0;j<=n;j++){
while(!deq.empty() && presum[j]<=presum[deq.back()]){//保证队列是单调的
deq.pop_back();
}
while(!deq.empty() && presum[j]-presum[deq.front()]>=k){
min_len=min(min_len,j-deq.front());
deq.pop_front();
}
deq.push_back(j);
}
if(min_len==n+1){
return -1;
}
else{
return min_len;
}
}
};
int main(){
vector<int> A;
int n,data;
cin>>n;
for(int i=0;i<n;i++){
cin>>data;
A.push_back(data);
}
int k;
cin>>k;
int res=Solution().shortestSubarray(A,k);
cout<<res<<endl;
return 0;
}
感谢
再次感谢我帅气耐心的宁同学！我真是个幸运的孩子，能遇见这么好的同学。
