ขนาด Subarray Sum ขั้นต่ำใน C++

สมมติว่าเรามีอาร์เรย์ขององค์ประกอบ n และจำนวนเต็มบวก s เราต้องหาความยาวน้อยที่สุดของ subarray ที่ต่อเนื่องกัน ซึ่งผลรวมจะมากกว่าหรือเท่ากับ s หากไม่มี ให้คืนค่า 0 แทน ดังนั้นหากอาร์เรย์เป็นเหมือน [2,3,1,2,3,4] และผลรวมเป็น 7 ผลลัพธ์จะเป็น 2 นี่คืออาร์เรย์ย่อย [4,3] มีความยาวขั้นต่ำสำหรับกรณีนี้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ans :=0, n :=ขนาดของอาร์เรย์ A, j :=0 และ sum :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • sum :=sum + A[i]

  • ในขณะที่ผลรวม – A[i]>=K และ j <=1

    • ผลรวม :=ผลรวม – A[j]

    • เพิ่มขึ้น 1

  • ถ้า sum>=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]

ผลลัพธ์

2