For example, given the array
[2,3,1,2,4,3]
and s = 7
,the subarray
[4,3]
has the minimal length under the problem constraint.
More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Naive Thinking: It seems this question is a typical two-pointer question. My idea is to keep a right boundary pointer and a left boundary pointer, keep sum up everything between two boundaries and move left boundary pointer and right pointer accordingly. One thing to be notice is that the left pointer needs to be checked if it can be moved forward each times right pointer finish its extension.
Run time is O(n).
Naive Thinking: It seems this question is a typical two-pointer question. My idea is to keep a right boundary pointer and a left boundary pointer, keep sum up everything between two boundaries and move left boundary pointer and right pointer accordingly. One thing to be notice is that the left pointer needs to be checked if it can be moved forward each times right pointer finish its extension.
Run time is O(n).
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int left = 0;
int right = 0;
int sum = 0;
int leng = 0;
int min_leng = nums.length+1;
while(right < nums.length){
// extend right boundary
while(sum < s && right < nums.length){
sum += nums[right++];
leng++;
}
if(sum >= s && leng < min_leng) min_leng = leng;
// extend left boundary
do{
sum -= nums[left++];
leng--;
if(sum >= s && leng < min_leng) min_leng = leng;
}while(sum >= s && left < right);
}
return min_leng==nums.length+1?0:min_leng;
}
}
The interesting part is the O(nlogn) run time solution. Even the run time is not efficient, it is still great practice to think it differently.
No comments:
Post a Comment