题解 | #和大于等于K的最短子数组#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @param k int整型 
     * @return int整型
     */
    public int shortestSubarray(ArrayList<Integer> nums, int k) {
        // write code here
        int[] pre = new int[nums.size()];
        pre[0] = nums.get(0);
        for (int i = 1; i < nums.size(); i++) {
            pre[i] = pre[i - 1] + nums.get(i);
        }
        // [i, j] 范围的子数组的和为 pre[j] - pre[i - 1]
        // [i, j] 范围的长度为 j - i + 1
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) >= k) {
                res = 1;
                break;
            }
            if (pre[i] >= k) {
                res = Math.min(res, i + 1);
                // [j + 1, i]
                for (int j = i - 2; j > -1; j--) {
                    if (pre[i] - pre[j] >= k) {
                        res = Math.min(res, i - j);
                        break;
                    }
                }
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}