LeetCode - Minimum Size Subarray Sum
Problem description
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
Example:
1
2
3
4
5
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Analysis
The first idea is to use sliding window and two pointer to do this.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int end = 0, start = 0;
int sum = 0;
int res = nums.length+1;
while (end < nums.length){
sum += nums[end];
if (sum >= s){
while (sum >= s){
res = Math.min(res, end-start+1);
sum -= nums[start];
start++;
}
}
end++;
}
return res > nums.length ? 0 : res;
}
}
Another method is to use prefix sum, and for each i, use binary search to find the corresponding sum[i] + target. And get an O(nlogn) algorithms.