C++での最小サイズのサブアレイの合計

n個の要素の配列と正の整数sがあるとします。連続するサブアレイの最小の長さを見つける必要があります。その合計はs以上です。存在しない場合は、代わりに0を返します。したがって、配列が[2,3,1,2,3,4]のようで、合計が7の場合、出力は2になります。これはサブ配列[4,3]がこの場合の最小の長さです。

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

• ans：=0、n：=配列Aのサイズ、j：=0および合計：=0

• 0からn–1の範囲のiの場合

  • 合計：=合計+ A [i]

  • 合計– A [i]>=Kおよびj<=1

    • 合計：=合計– A [j]

    • jを1増やします

  • 合計>=kの場合、

    • ans =0またはans>（i – j + 1）の場合、ans：=（i – j + 1）

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minSubArrayLen(int K, vector<int>& A) {
      int ans = 0;
      int n = A.size();
      int j = 0;
      int sum = 0;
      for(int i = 0; i < n; i++){
         sum += A[i];
         while(sum - A[j] >= K && j <= i){
            sum -= A[j];
            j++;
         }
         if(sum >= K){
            if(ans == 0 || ans > (i - j + 1)) ans = (i - j + 1);
         }
      }
   return ans;
   }
};
main(){
   vector<int> v = {2,3,1,2,4,3};
   Solution ob;
   cout << ((ob.minSubArrayLen(7,v)));
}

入力

7
[2,3,1,2,4,3]

出力

2