Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
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.A:
two pointer
public class Solution { public int minSubArrayLen(int s, int[] nums) { if(nums == null || nums.length==0) return 0; int p1 =0,p2= -1; // both are inclusive int minLen = Integer.MAX_VALUE; long sum = 0; while(p2<nums.length){ if(sum < s){ p2++; if(p2<nums.length) sum += nums[p2]; }else{ minLen = Math.min(minLen, p2-p1+1); sum -= nums[p1++]; // do not need to check if p1<=p2, coz they s is positive } } return minLen==Integer.MAX_VALUE?0:minLen; } }
Mistakes:
这道题的2大错误在于。
1: 刚开始用了 以前的双层循环的解法。 虽然复杂的没有变,但是写起来复杂了。 不好
2: 核心错误: 一开始p2没有确定是inclusive的,因此,开始没有设p2= -1;
***********第二遍*********
public class Solution { public int minSubArrayLen(int s, int[] nums) { int res = Integer.MAX_VALUE, pre = -1, sum = 0; for(int i =0;i<nums.length;i++){ sum+= nums[i]; if(sum<s) continue; while( sum-nums[pre+1] >= s){ pre++; sum -= nums[pre]; } res = Math.min(i-pre,res); sum = sum - nums[++pre]; } return res == Integer.MAX_VALUE? 0 : res; } }
No comments:
Post a Comment