209. 长度最小的子数组

209. 长度最小的子数组

209. 长度最小的子数组

方法一：暴力法

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = nums.length + 1 ;
        int sublength = 0;
        int sum = 0;
        for(int i = 0;i < nums.length;i++){
            sum = 0;
            for(int j = i;j < nums.length;j++){
                sum += nums[j];
                if(sum >= target){
                    sublength = j -i + 1;
                    result = result < sublength ? result : sublength;
                    break;
                }

            }
        }
        return result == nums.length + 1 ? 0 : result;
    }
}

方法二：滑动窗口法

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE ;
        int left = 0,right=0;
        int sum = 0;
        while(right < nums.length){
            sum += nums[right++];
            while(sum >= target){
                result = result < (right - left) ? result : (right - left);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

方法三：二分法

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE ;
        int[] sums = new int[nums.length + 1];
        for(int i = 1;i <= nums.length;i++){
            sums[i] = sums[i-1] + nums[i-1];
        }
        for(int i = 0;i <= nums.length;i++){
            int s = target + sums[i];
            int index = Arrays.binarySearch(sums, s);
            if(index < 0){
                index = ~index;
            }
            if(index <= nums.length){
                result = result < index - i ? result : index - i;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}