一、环境说明

1. 本文是 LeetCode 862. 和至少为 K 的最短子数组，使用C++实现。
2. 单调双端队列+前缀和数组
3. 测试环境:Visual Studio 2019。

二、代码展示

c++代码

class Solution {
public:int shortestSubarray(vector& nums, int k) {int n = nums.size();vector pre(n+1);//大小为n+1的一位堆空间prefor(int i = 1;i<=n;i++){pre[i]=pre[i-1] + nums[i-1];//生成前缀和数组，大小为n+1,从pre[0]=0开始。}int ans = n+1;deque qu;//双端队列for(int i = 0;i<=n;i++){//初始情况，qu为空，0号位置直接入队while(!qu.empty()&&pre[i]-pre[qu.front()]>=k){//当前位置前缀和-队首前缀和>=kans = min(ans,i-qu.front());//判断最小长度qu.pop_front();}while(!qu.empty()&&pre[i]<=pre[qu.back()]){//当前位置前缀和<=队尾前缀和qu.pop_back();}qu.push_back(i);//每次循环，当前位置入队尾}return ans >= n+1?-1:ans;//不存在，返回-1//存在，返回长度}
};

三、思路分析

暴力循环TLE分析

想象暴力循环，先下结论，二次遍历，时间复杂度是O(n2)O(n^2)O(n2)，对于本题规模，TLETLETLE。

• 分析暴力循环(可以不看)：需要首先要遍历numsnumsnums，当前位置i。对每个nums[i]nums[i]nums[i]，为了得到他的最短子数组>=k>=k>=k，我们要从iii往右，进行第二次遍历，二次遍历位置初始化j=i+1j=i+1j=i+1。对于位置iii，初始化sum=nums[i]sum=nums[i]sum=nums[i]，二次遍历一路向右sum＋=nums[j]sum＋=nums[j]sum＋=nums[j]，直到sum>=ksum>=ksum>=k。才得到一个位置。这样二次遍历，细节繁杂，而且时间复杂度是O(n2)O(n^2)O(n2)。

为什么是前缀和

(重要)前缀和性质:

• pre[right]−pre[left]=leftpre[right]-pre[left]=leftpre[right]−pre[left]=left到rightrightright 上所有元素之和。

(可以不看)如果利用前缀和，可以简化暴力循环sum+=nums[j]sum+=nums[j]sum+=nums[j]判断过程。

• 声明前缀和数组pre[n+1]pre[n+1]pre[n+1]存储每个数的前缀和。
• pre[0]存一个0pre[0]存一个0pre[0]存一个0，表示nums[−1]nums[-1]nums[−1]位置没数，后续如果pre[i]=kpre[i]=kpre[i]=k，iii可以参与答案比较，这要感谢pre[0]pre[0]pre[0]。
• pre[n]pre[n]pre[n]对应numsnumsnums中n−1n-1n−1位置的前缀和，所以pre[n]=pre[n−1]+nums[n−1]pre[n] = pre[n-1]+nums[n-1]pre[n]=pre[n−1]+nums[n−1]。

双端队列

超详细图解，见灵茶山艾府-两张图秒懂单调队列

代码流程

1. 一次遍历numsnumsnums，得到前缀和。
2. 双端队列,从前往后入队
3. 当前位置iii，每次向后移动，当前数入队尾
4. whilewhilewhile当前位置前缀和-队首前缀和>=k>=k>=k，判断最小长度。队首元素出队。
5. whilewhilewhile当前位置前缀和<=<=<=队尾前缀和，队尾出队。

四、博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

五、AC

六、复杂度分析

1. 时间复杂度:O(n)O(n)O(n) ,nnn是nums长度。看双端队列的循环，外层for循环每次入队一个数，while循环只进行出队操作，每个前缀和pre[i]，最多入队一次，出队一次，时间复杂度不会超过O(n)O(n)O(n)。
2. 空间复杂度:O(n)O(n)O(n),前缀和preprepre和双端队列quququ的空间复杂度都是O(n)O(n)O(n)。