Tổng kích thước tối thiểu của mảng con trong C ++

Giả sử chúng ta có một mảng gồm n phần tử và một số nguyên dương s. Chúng ta phải tìm độ dài nhỏ nhất của một mảng con liền kề, trong đó tổng lớn hơn hoặc bằng s. Nếu không có, hãy trả về 0. Vì vậy, nếu mảng giống như [2,3,1,2,3,4] và tổng là 7, thì đầu ra sẽ là 2. Đây là mảng con [4,3] có độ dài tối thiểu cho trường hợp này.

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

• ans:=0, n:=kích thước của mảng A, j:=0 và sum:=0

• cho tôi trong phạm vi từ 0 đến n - 1

  • sum:=sum + A [i]

  • while sum - A [i]> =K và j <=1

    • sum:=sum - A [j]

    • tăng j lên 1

  • nếu sum> =k thì

    • nếu ans =0 hoặc ans> (i - j + 1), thì ans:=(i - j + 1)

• trả 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 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)));
}

Đầu vào

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

Đầu ra

2