Friday, June 12, 2015

Minimum Size Subarray Sum

Q:
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