Algorithm
Problem Name: 209. Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray (A subarray is a contiguous non-empty sequence of elements within an array.) whose 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 <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int minSubArrayLen(int s, int* nums, int numsSize) {
int i, j, k, d = 0;
k = 0;
for (i = 0, j = 0; i < numsSize; i ++) {
k += nums[i];
while (k >= s) {
// found it
if (d == 0 || d > i - j + 1) {
d = i - j + 1;
}
// try to shrink the window from left pointer
k -= nums[j ++];
}
}
return d;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int i = 0, j = 0, sum = 0, len = nums.size();
while(j < nums.size()){
while(j < nums.size() && sum < s) sum += nums[j++];
if(i == 0 && sum < s> return 0;
while(sum - nums[i]>= s) sum -= nums[i++];
len = min(len, j - i);
sum -= nums[i++];
}
return len;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int sum = 0;
int slow = 0;
int fast = 0;
int n = nums.length;
int minLen = Integer.MAX_VALUE;
while (fast < n) {
sum += nums[fast];
if (sum >= s) {
while (slow <= fast) {
minLen = Math.min(minLen, fast - slow + 1);
if (sum - nums[slow] >= s) {
sum -= nums[slow];
slow++;
}
else {
break;
}
}
}
fast++;
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const minSubArrayLen = function(s, nums) {
let sum = 0, from = 0, win = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
while (sum >= s) {
win = Math.min(win, i - from + 1);
sum -= nums[from++];
}
}
return (win === Number.MAX_SAFE_INTEGER) ? 0 : win;
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minSubArrayLen(self, s, nums):
l, res, curr = 0, len(nums) + 1, 0
for r, num in enumerate(nums):
curr += num
while curr >= s: res, l, curr = min(res, r - l + 1), l + 1, curr - nums[l]
return res < len(nums) + 1 and res or 0
Input
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0209_MinimumSizeSubarraySum
{
public int MinSubArrayLen(int s, int[] nums)
{
var result = int.MaxValue;
var sum = 0;
var left = 0;
for (int i = 0; i < nums.Length; i++)
{
sum += nums[i];
while (sum >= s)
{
result = Math.Min(result, i - left + 1);
sum -= nums[left++];
}
}
return result == int.MaxValue ? 0 : result;
}
}
}
Input