165. Minimum Size Subarray Sum

Grow a window on the right to add sum; the moment the sum reaches target, shrink from the left as far as possible while still meeting target, recording the smallest width seen. Because all numbers are positive, expanding always increases the sum and shrinking always decreases it.

Idea

All values are positive, which makes a sliding window work: extending the window on the right only ever increases the sum, and shrinking on the left only ever decreases it. So we can greedily keep the window as small as possible while its sum stays >= target.

Algorithm

1. Maintain a window [left..right], a running total, and best = ∞.
2. Move right across the array, adding nums[right] to total.
3. Whenever total >= target, the window qualifies: record best = min(best, right - left + 1), then remove nums[left] and advance left to try an even smaller window.
4. At the end, return best if it was ever updated, else 0.

Each index enters the window once (via right) and leaves at most once (via left), so the whole scan is linear.

Worked example: target = 7, nums = [2,3,1,2,4,3]

The smallest qualifying window is [4,3] of length 2.

Complexity

• Time: O(n) — each element is added and removed at most once.
• Space: O(1).

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, total = 0, best = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            total += nums[right];
            while (total >= target) {
                best = Math.min(best, right - left + 1);
                total -= nums[left];
                left++;
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}