题解 | #长度最小的连续子数组#

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 len = nums.length; // 定义一个整型变量，用于存放 nums 数组的长度
        if (1 == len) {
            return nums[0] >= target ? 1 : 0;
        }
        // [i, j] 范围内的和等于 prefix[j] - prefix[i - 1]
        // [i, j] 范围的长度等于 j - (i - 1)
        int[] prefix = new int[len]; // 定义一个整型数组，用于存放前缀和
        int res = len + 1; // 定义一个整型变量，用于存放最终的返回结果
        for (int i = 0; i < len; i++) { // 获取前缀和
            int tmp = nums[i]; // 获取当前位置上的数字
            if (tmp >= target) { // 如果当前位置上的数字已经大于等于 target 了，那么不就是长度最小的连续子数组嘛(长度为 1)
                return 1;
            }
            if (i == 0) { // 0 位置上的前缀和就是它自己
                prefix[i] = nums[i];
            }
            else {
                prefix[i] = prefix[i - 1] + nums[i];
            }
            if (prefix[i] >= target) { // 如果当前位置上的前缀和大于等于 target
                int index = i - 1; // 当前位置的前一位
                // 求 [index, i] 范围的连续子数组的和
                while (index > 0) { // 不越界
                    if (prefix[i] - prefix[index - 1] >= target) {
                        res = Math.min(res, i - (index - 1));
                        break;
                    }
                    index--;
                }
                if (index == 0) { // 如果最终 index == 0 了，那么证明只有 [0, i] 范围内的连续子数组的和大于等于 target
                    res = Math.min(res, i + 1);
                }
            }
        }
        return res == len + 1 ? 0 : res; // 如果 res 没有更新过，那就证明，即使将整个数组中的数字求和，一样做不到大于等于 target，那么直接返回 0
    }
}