Back to Sliding Window
Medium
Minimum Size Subarray Sum
Given an array of positive integers `nums` and a positive integer `target`, return the minimal length of a subarray whose sum is greater than or equal to `target`. If there is no such subarray, return 0 instead.
Examples
Input:target = 7, nums = [2,3,1,2,4,3]
Output:2
The subarray [4,3] has the minimal length under the problem constraint.
Input:target = 4, nums = [1,4,4]
Output:1
The subarray [4] has length 1.
Constraints
1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^4
Approach
Check all possible subarrays. For each subarray, calculate its sum. If the sum is greater than or equal to the target, update the minimum length found so far.
Complexity Analysis
Time Complexity
O(n^2)
Space Complexity
O(1)
This approach is straightforward but slow and will cause TLE for large inputs.
Solution.java
class Solution { public int minSubArrayLen(int target, int[] nums) { int minLength = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { int currentSum = 0; for (int j = i; j < nums.length; j++) { currentSum += nums[j]; if (currentSum >= target) { minLength = Math.min(minLength, j - i + 1); break; // No need to check longer subarrays starting at i } } } return minLength == Integer.MAX_VALUE ? 0 : minLength; }}