Subarray ngắn nhất với Sum ít nhất K trong C ++

Giả sử chúng ta có một mảng A. Chúng ta phải tìm độ dài của mảng con ngắn nhất, không rỗng, liền kề của A có tổng ít nhất là K. Nếu không có mảng con đó, thì trả về -1.

Vì vậy, nếu đầu vào là [5,3, -2,2,1] và k =6, thì đầu ra sẽ là 2, như chúng ta thấy (5 + 3)> =6

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của A

• ans:=n + 1, j:=0, sum:=0

• Xác định một dq deque

• để khởi tạo i:=0, khi i

  • nếu tôi> 0, thì -

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

  • nếu A [i]> =K, thì -

    • ans:=tối thiểu ans và i + 1

  • while (không phải dq trống và của A [i] - phần tử đầu tiên A [dq]> =K), do -

    • ans:=tối thiểu ans và phần tử đầu tiên của i - dq

    • xóa phần tử phía trước khỏi dq

  • while (không phải dq trống và A [i] <=phần tử cuối cùng của A [dq], do -

    • xóa phần tử cuối cùng khỏi dq

  • chèn tôi vào cuối dq

• return (nếu ans giống n + 1 thì -1, ngược lại ans)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{5,3,-2,2,1}, 6

Đầu ra

2