LintCode：M-和大于S的最小子數組

LintCode連結

給定一個由 n 個整數組成的數組和一個正整數 s ，請找出該數組中滿足其和 ≥ s 的最小長度子數組。如果無解，則傳回 -1。

您在真實的面試中是否遇到過這個題？  Yes 樣例

給定數組 

[2,3,1,2,4,3]

 和 s = 

7

, 子數組 

[4,3]

 是該條件下的最小長度子數組。

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
       return helper(nums, s);
    }
    
    //雙指針
    //TC = O(n)
    int helper(int[] nums, int s){
        int n = nums.length;
        
        int minLen=Integer.MAX_VALUE;
        int start=0;
        int end=0;
        int sum=0;
        while(end<n){
            sum+=nums[end];
            if(sum>=s){
                while(sum>=s && start<=end){
                    minLen = Math.min(minLen, end-start+1);
                    sum-=nums[start++];
                }
            }
            end++;
        }
        
        return minLen==Integer.MAX_VALUE?-1:minLen;
    }
    
    //枚舉
    //TC = O（n^2）
    //SC = O（n）
    int helper_enum(int[] nums, int s){
        int n = nums.length;
        int[] sums = new int[n];
        
        for(int i=0; i<n; i++){
            if(i==0)
                sums[0] = nums[0];
            else   
                sums[i] = sums[i-1]+nums[i];
            
            if(nums[i]>=s)
                return 1;
        }
        
        for(int len=2; len<=n; len++){
            for(int i=0; i+len-1<n; i++){
                int j=i+len-1;
                int tmp = sums[j]-((i==0)?0:sums[i-1]);
                if(tmp>=s)
                    return len;
            }
        }
        
        return -1;
    }
}