मान लीजिए हमारे पास n तत्वों की एक सरणी और एक धनात्मक पूर्णांक s है। हमें एक सन्निकट उपसरणी की न्यूनतम लंबाई ढूंढनी है जिसका योग s से बड़ा या बराबर हो। यदि ऐसी कोई उपसरणी नहीं है, तो 0 लौटाएँ।
उदाहरण: सरणी [2,3,1,2,4,3], s = 7 → आउटपुट 2 (उपसरणी [4,3] का योग 7)।
स्लाइडिंग विंडो (दो पॉइंटर्स)
ans = 0, sum = 0, left = 0।right = 0 से n-1तक:sum += A[right]।while sum - A[left] >= s:sum -= A[left],left++।
- यदि
sum >= s:ans = (ans == 0) ? (right-left+1) : min(ans, right-left+1)।
ansलौटाएँ।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ans = 0, sum = 0, left = 0;
for (int right = 0; right < n; right++) {
sum += nums[right];
while (sum - nums[left] >= target) {
sum -= nums[left];
left++;
}
if (sum >= target) {
if (ans == 0 || ans > right - left + 1) {
ans = right - left + 1;
}
}
}
return ans;
}
};
int main() {
vector<int> v = {2,3,1,2,4,3};
Solution ob;
cout << ob.minSubArrayLen(7, v); // 2
return 0;
}
इनपुट
7 [2,3,1,2,4,3]
आउटपुट
2