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.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4] Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0
Constraints:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
Minimum Size Subarray Sum Solutions
✅Time: O(n)
✅Space: O(1)
C++
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int ans = INT_MAX;
int sum = 0;
for (int l = 0, r = 0; r < nums.size(); ++r) {
sum += nums[r];
while (sum >= s) {
ans = min(ans, r - l + 1);
sum -= nums[l++];
}
}
return ans < INT_MAX ? ans : 0;
}
};
Java
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int ans = Integer.MAX_VALUE;
int sum = 0;
for (int l = 0, r = 0; r < nums.length; ++r) {
sum += nums[r];
while (sum >= s) {
ans = Math.min(ans, r - l + 1);
sum -= nums[l++];
}
}
return ans != Integer.MAX_VALUE ? ans : 0;
}
}
Python
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
ans = math.inf
sum = 0
j = 0
for i, num in enumerate(nums):
sum += num
while sum >= s:
ans = min(ans, i - j + 1)
sum -= nums[j]
j += 1
return ans if ans != math.inf else 0
Watch Tutorial
Checkout more Solutions here