[LintCode] 406 Minimum Size Subarray Sum 解题报告

Description
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 -1 instead.



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.


Challenge
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).


思路
这是一道“前向型”指针的题。我们维护两个指针i和j从头往下走。
同时，我们维护一个从i一直加到j-1的sum。
我们知道如果从index a加到index b都小于s，那么index a + 1加到index b肯定也是小于s的。这样我们就可以避免重复计算从index a + 1到index b这段。
如果我们发现sum > s，那么(j - 1) - i + 1 = j - i 就是组成这个sum的length了。我们需要一直遍历到最后，找到最小的length。


Code

public class Solution {
    /**
     * @param nums: an array of integers
     * @param s: an integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        // write your code here
        
        int min = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        int sum = 0;
        for (i = 0; i < nums.length; i++) {
            while (j < nums.length && sum < s) {
                sum += nums[j];
                j++;
            }
            if (sum >= s) {
                min = Math.min(min, j - i);
            }
            sum -= nums[i];
        }
        if (min == Integer.MAX_VALUE) {
            return -1;
        }
        return min;
    }
}