Minimum Size Subarray Sum- Medium - NL
Published:
Question
- https://leetcode.com/problems/minimum-size-subarray-sum/
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Approach
- Moving window algorithm
Solution
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if (n==0) {
return 0;
}
int i = 0;
int j = 0;
int sum = 0;
int wind = INT_MAX;
int fl=0;
while(j<n && i<=j) {
sum += nums[j];
while(i<j && sum>=target) {
sum -= nums[i];
if (sum >= target) {
i++;
} else {
sum += nums[i];
break;
}
}
if (sum >= target && wind > (j-i)) {
fl = 1;
wind = j-i+1;
}
cout<<i<<" "<<j<<endl;
j++;
}
if (fl==0) {
return 0;
}
return wind;
}
};