Minimum Size Subarray Sum

Find the shortest run of positive numbers whose sum is at least target: grow the window until it is enough, then shrink it from the left.

The idea

Every number is positive, so adding on the right only raises the sum and dropping on the left only lowers it. Grow the window until the sum reaches target. Then it is a candidate, and the only way to find a shorter one ending here is to drop from the left, so shrink while the sum still reaches target, recording the length each time.

Code

public static int MinSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, best = int.MaxValue;
    for (int right = 0; right < nums.Length; right++) {
        sum += nums[right];
        while (sum >= target) {
            best = Math.Min(best, right - left + 1);
            sum -= nums[left++];
        }
    }
    return best == int.MaxValue ? 0 : best;
}

Tips

• Record the length before shrinking: the window is valid right now, and the next drop may make it invalid.
• The trick needs positive numbers. With negatives, dropping from the left could raise the sum, and you need prefix sums with a monotonic deque instead.
• Return 0, not int.MaxValue, when no window ever reaches the target.

In the .NET library

int.MaxValue is the "nothing found yet" marker, so Math.Min works from the first valid window without a special case.