下载掌阅APP，畅读海量书库
立即打开
给定数组 A 和 K ，返回数组 A 的总和至少为 K 的最短非空连续子数组的长度。如果没有总和至少为 K 的非空子数组，则返回-1。
例1
输入： A =[1]， K =1
输出：1
例2
输入： A =[1，2]， K =4
输出：-1
例3
输入： A =[2，-1，2]， K =3
输出：3
思路：以 A =[84，-37，32，40，95]， K =167为例进行求解。
第一步：初始化队列的第一个元素，（-1，0）中第一个值是数组的索引，第二个值是前缀和。初始化右指针 j =0。
第二步：前缀和cumsum=84，因为不满足出队列的条件，所以（0，84）进入队列。
第三步：继续移动右指针， j =1，此时cumsum=47，队列中84大于47，所以（0，84）出队，（1，47）进入队列。
第四步：继续移动右指针， j =2，此时cumsum=79，继续把（2，79）压入队列。
第五步：继续移动右指针， j =3，此时cumsum=119，继续把（3，119）压入队列。
第六步：继续移动右指针， j =4，此时cumsum=214，大于167，首先计算得到min_size=5。把第一个元素移出队列，此时队列中的第一个元素为（1，47），cumsum-47=167，则有min_size=3。
代码清单4-5 求和大于 K 的最短非空连续子数组的长度
时间复杂度为 O （ n ），空间复杂度为 O （ n ）。