C++에서 합이 최소 K인 최단 하위 배열

배열 A가 있다고 가정합니다. 합이 K 이상인 A의 가장 짧고 비어 있지 않은 연속 하위 배열의 길이를 찾아야 합니다. 그러한 하위 배열이 없으면 -1을 반환합니다.

따라서 입력이 [5,3,-2,2,1]이고 k =6이면 출력은 (5+3)>=6

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=A의 크기

• ans :=n + 1, j :=0, 합계 :=0

• 하나의 데크 dq 정의

• initialize 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에서 앞 요소 삭제

  • 동안 (dq가 비어 있지 않고 A[i] <=A[dq]의 마지막 요소인 경우 -

    • dq에서 마지막 요소 삭제

  • dq 끝에 i 삽입

• 반환(as가 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