假设我们有一个数组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