题目主要信息

1、给定一个数组 nums 和一个正整数 target

2、找出满足和大于等于 target 的长度最短的连续子数组

方法一:暴力解法

具体方法

由于本题中数据不大，因此可以采取暴力解法。 计算所有i开始，j结尾的数组的和，若大于target，则计算其长度并和最小值进行比较。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int minSubarray (int[] nums, int target) {
        // write code here
        int ans = Integer.MAX_VALUE;
        for(int i=0; i<nums.length; i++){
            int sum = 0;
            for(int j=i; j<nums.length; j++){
                sum+=nums[j];  //累计求和
                if(sum>=target){
                    ans = Math.min(j-i+1, ans);
                    break;
                }
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，其中n为数组长度
• 空间复杂度：$O(1)O(1)$

方法二：滑动窗口

具体方法

由于所求子数组为连续子数组，因此可以用滑动窗口来解决该问题。为了保证窗口内的和大于target且最小，因此，定义滑动窗口的移动方法如下：

当窗口内的和大于target时，右移左边界

当窗口内的和小于target时，右移右边界

只需保存滑动窗口的最小长度即可

具体如图所示：

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int minSubarray (int[] nums, int target) {
        // write code here
        int l = 0;
        int r = 0;
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        while(r < nums.length){
            while(r<nums.length && sum<target){  #和小于target，右移右边界
                sum+=nums[r];
                r++;
            }
            while(l<r && sum>=target){  #和大于target，右移左边界
                ans = Math.min(ans, r-l);
                sum-=nums[l];
                l++;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$