C ++中最小K总和最短的子数组
假设我们有一个数组A。我们必须找到A的最短，非空，连续子数组的长度，其总和至少为K。如果没有这样的子数组，则返回-1。
因此，如果输入类似于[5,3，-2,2,1]且k=6，则输出将为2，如我们所见（5+3）>=6
为了解决这个问题，我们将遵循以下步骤-
n：=A的大小
ans：=n+1，j：=0，和：=0
定义一个双端队列dq
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
从dq中删除最后一个元素
ans：=ans和i-dq的第一个元素的最小值
从dq中删除前元素
ans：=ans和i+1的最小值
A[i]：=A[i]+A[i-1]
如果i>0，则-
如果A[i]>=K，则-
而（不是dq为空且A[i]-第一元素A[dq]>=K），则执行-
而（不dq为空，并且A[i]<=A[dq]的最后一个元素，则执行-
在dq的末尾插入i
返回（如果ans与n+1相同，则为-1，否则为ans）
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int shortestSubarray(vector<int> &A, int K) {
int n = A.size();
int ans = n + 1;
int j = 0;
int sum = 0;
deque<int> dq;
for (int i = 0; i < n; i++) {
if (i > 0)
A[i] += A[i - 1];
if (A[i] >= K) {
ans = min(ans, i + 1);
}
while (!dq.empty() && A[i] - A[dq.front()] >= K) {
ans = min(ans, i - dq.front());
dq.pop_front();
}
while (!dq.empty() && A[i] <= A[dq.back()])
dq.pop_back();
dq.push_back(i);
}
return ans == n + 1 ? -1 : ans;
}
};
main(){
Solution ob;
vector<int> v = {5,3,-2,2,1};
cout << (ob.shortestSubarray(v, 6));
}输入值
{5,3,-2,2,1}, 6输出结果
2