209 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

C# Solution¶

using System;
using System.Linq;

namespace Algorithms.Medium
{
  public class MinimumSizeSubarraySum
  {
    public static int FindArrayLength(int[] nums, int target)
    {
      var l = 0;
      var total = 0;
      var ans = nums.Length + 1;

      foreach (var r in Enumerable.Range(0, nums.Length))
      {
        total += nums[r];
        while (total >= target)
        {
          ans = Math.Min(ans, r - l + 1);
          total -= nums[l];
          l++;
        }
      }

      return ans == nums.Length + 1 ? 0 : ans;
    }
  }
}

C# Tests¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class MinimumSizeSubarraySumTests
  {
    [Fact]
    public void FoundTest1()
    {
      Assert.Equal(2, MinimumSizeSubarraySum.FindArrayLength(new int[] { 2, 3, 1, 2, 4, 3 }, 7));
    }

    [Fact]
    public void FoundTest2()
    {
      Assert.Equal(1, MinimumSizeSubarraySum.FindArrayLength(new int[] { 1, 4, 4 }, 1));
    }

    [Fact]
    public void NotFoundTest1()
    {
      Assert.Equal(0, MinimumSizeSubarraySum.FindArrayLength(new int[] { 1, 1, 1, 1, 1, 1, 1, 1 }, 11));
    }
  }
}