C++で最小Kの合計を持つ最短のサブアレイ

配列Aがあるとします。合計が少なくともKであるAの最短で空でない連続したサブ配列の長さを見つける必要があります。そのようなサブ配列がない場合は、-1を返します。

したがって、入力が[5,3、-2,2,1]のようで、k =6の場合、（5 + 3）> =6

これを解決するには、次の手順に従います-

• n：=Aのサイズ

• ans：=n + 1、j：=0、sum：=0

• 1つのdequedqを定義する

• 初期化i：=0の場合、i

  • i> 0の場合、-

    • A [i]：=A [i] + A [i-1]

  • A [i]> =Kの場合、-

    • ans：=最小のansとi + 1

  • （dqが空ではなく、A[i]-最初の要素A[dq]> =K）の場合、-

    • ans：=ansの最小値とiの最初の要素--dq

    • dqからフロント要素を削除します

  • while（dqが空ではなく、A [i] <=A [dq]の最後の要素、do-

    • dqから最後の要素を削除する

  • dqの最後にiを挿入します

• return（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