leetcode-0209:长度最小的子数组

题目：

leetcode-0209:长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

题解

暴力法直接给整出来了。

明天想想别的方法

public class Solution0209 {
    /*
    * 题目：209. 长度最小的子数组
    *
    *       给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
    *
    * 思考过程：
    *
    *       因为这个数组因为是不确定的。要求的其中满足和大于等于s的连续子数组。所以这么说来直接的想法就是针对每个点都往前计算它刚好大于s的长度。
    * */
    public static void main(String[] args) {
        Solution0209 solution0209 = new Solution0209();
        System.out.println(solution0209.minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
        System.out.println(solution0209.minSubArrayLen(4, new int[]{1,4,4}));

    }
    public int minSubArrayLen(int s, int[] nums) {
        int min_length = nums.length+1;
        int cur_sum = 0;
        for (int i = 0; i < nums.length; i++){
            // 以这个节点向左边出发找刚好大于s的长度
            cur_sum = nums[i];
            if (cur_sum >= s){
                return 1;
            }
            for (int j = i-1; j>-1;j--){
                cur_sum +=nums[j];
                if (cur_sum >= s){
                    if(i-j+1<min_length){
                        min_length = i-j+1;
                    }
                    break;
                }
            }
        }
        if (min_length == nums.length+1){
            return 0;
        }
        return min_length;
    }
}

队列

这个方法也是刚开始也就能够想到的，其实和滑窗也是类似。

但是这里它写的更为巧妙地里外两个循环，分别控制left和right；

public int minSubArrayLen2(int s, int[] nums) {
    int right = 0;
    int left = 0;
    int sum = 0;
    int min = nums.length+1;
    while (left < nums.length){
        sum += nums[left++];
        while (sum>=s){
            min = Math.min(min, left - right);
            sum -= nums[right++];
        }
    }
    return min == nums.length+1 ? -1:min;
}