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