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)
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]