Minimum Size Subarray Sum

This is a leetCode problem: http://www.programcreek.com/2014/05/leetcode-minimum-size-subarray-sum-java/

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 of 2 under the problem constraint.

We can solve this by a sliding window, aka inch worm algorithm. Essentially we grow this sliding window to the right if the sum is smaller than the s, once sum >= s, then we update the minimal length of the window and then start to shrink the window from the left until sum < s. Here is the code:

Longest Continuous Ones of a String contains 0 or 1 - inch worm algorithm

Given a string consisted of only 0 or 1, and a number N.

We have N times to flip 0 to 1 in array. Find the longest continuous 1 after we flipped the N zero elements. Rotation is allowed.

For example, 100100111000, n=2, the best flip is 100111111000, return 6

10001101101, n=2, the best flip is 10001111111, return 8(rotation is allowed)

The following algorithm is more like a inch worm walking on a line, it tries to go forward as it can, then shrink from the tail, then move forward again.

/**
     * we first concatenate string to itself
     *
     * then use a sliding window, keep track of number of 0s in the window
     * grow the right side of window if not exceed max 0s allowed
     * otherwise shrink the left side to reduce the 0s
     *
     * the algorithm stops when left side reach the length of original string
     *
     */
    public static int maxContinuous1sWithRotation(String s, int maxFlips){
        int p1=0, p2=0, len = s.length(), num0=0, max=0;
        while(p1<len && p2-p1<len){
            if(s.charAt(p2%len) == '0'){
                num0++;
            }
           
            /*
             * if num0 reaches maxFlips+1
             * we need to shrink the sliding window from left
             * until we reaches a 0 and reduce the counter
             */
            if(num0 > maxFlips){               
                while(p1<len && s.charAt(p1)=='1')
                    p1++;
                p1++; num0--;
            }
           
            /*
             * we keep on growing the sliding window
             * to the right and update the max
             */
            p2++;
            max = Math.max(max, p2-p1);       
        }
        return max;
    }