题目地址：https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
题目描述
Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.
Ifthere 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；
题目大意
求最短的子数组长度，使得这个子数组的和最少为K，如果不存在这样的子数组，返回-1.
解题方法
队列
我尝试了O(N^2)的解法，果然超时了。也对，题目给出的数组长度是50000，基本上只有O(N)或者O(NlogN)的时间复杂度才行了。
这个题的做法要感谢lee215和演员的自我修养。下面的内容来自演员的自我修养open in new window。
分析：
1、 显然，我们会想到使用dp[i]记录sum(A[:i])，那么这道题就变成了，给定一个数组dp,找到一组i,j，使得dp[j]-dp[i]>=K，且j-i尽量小！；
2、 数据长度达到50000，显然不能使用O(n^2)复杂度的方法，我们得想办法让i,j只走一遍；
3、 用一个简单的示例来分析，设A=[4,-1,2,3],，K=5，那么dp=[0,4,3,5,8]，我们从dp数组的第2个数开始分析，（假设来了个-1，那么因为-1比0小，后面任意一个数val如若满足val-0>K,那么val+1也一定大于K，且-1所在的位置i显然能获得更优解，所以0这个位置就失去了意义），现在考虑示例，来了个4，我们发现4-0小于5，我们怎么对4进行处理呢，因为考虑到之后或许会出现一个足够大的数，比如9，那么4相对于0是更优的，但也有可能只来一个8，那么4就没作用了，所以先暂且保留观察等到来了一个5以上的数，我们依次对保留的数（目前是0，4）进行判断得最优解；
4、 接下来来了个3，那么根据上面提到的论点，4将会被舍弃，但3比0要大，故此时0，3保留；
5、 然后来了个5，5-0>=5，故找到一组i,j，记录下来，然后判断5-3>=5?如若确实大于，即再次找到一组i,j，若小于，则5保留（考虑到之后或许来了个10），依次类推；
思路：
1、 建立一个队列记录保留数字，初始为0；
2、 依次对dp中的数进行分析，如果dp[i]-dp[Q[0]]>=K，则记录一次i,j；
3、 如果dp[i]<dp[Q[-1]]，则舍弃Q[-1]；
C++代码如下：
class Solution {
public:
int shortestSubarray(vector<int>& A, int K) {
const int N = A.size();
vector<int> preSum(N + 1, 0);
for (int i = 1; i < N + 1; i++) {
preSum[i] = preSum[i - 1] + A[i - 1];
}
int res = INT_MAX;
deque<int> q;
q.push_back(0);
for (int i = 1; i < N + 1; i++) {
int a = preSum[i];
while (!q.empty() && a - preSum[q.front()] >= K) {
res = min(res, i - q.front());
q.pop_front();
}
while (!q.empty() && a < preSum[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
return res == INT_MAX ? -1 : res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
参考资料：
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C%2B%2BJavaPython-O(N)-Using-Deque https://buptwc.com/2018/07/02/Leetcode-862-Shortest-Subarray-with-Sum-at-Least-K/
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发