ধরা যাক n উপাদানের একটি অ্যারে এবং একটি পজিটিভ ইন্টিজার s আছে। আমরা একটি সংলগ্ন সাবঅ্যারের ন্যূনতম দৈর্ঘ্য বের করব যার সমষ্টি s-এর চেয়ে বড় বা সমান। যদি এমন কোনো সাবঅ্যারে না থাকে, তবে 0 রিটার্ন করব। যদি অ্যারে হয় [2,3,1,2,3,4] এবং sum হয় 7, তবে আউটপুট হবে 2। কারণ সাবঅ্যারে [4,3]-এর দৈর্ঘ্য ন্যূনতম এই কেসে।
সমাধানের ধাপগুলো −
ans := 0, n := অ্যারে A-এর আকার, j := 0 এবং sum := 0
i = 0 থেকে n-1 পর্যন্ত
sum := sum + A[i]
যখন sum - A[j] >= K এবং j <= i
sum := sum - A[j]
j ১ বাড়াব
যদি sum >= K হয়, তবে
যদি ans = 0 হয় বা ans > (i - j + 1) হয়, তবে ans := (i - j + 1)
ans রিটার্ন করব
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#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
