题解 | #牛群保卫战# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param nums int整型一维数组
     * @return int整型
     */
    public int findMinSubarrayLength (int target, int[] nums) {
        // write code here
        int minLength = Integer.MAX_VALUE;
        int[] prefixSum = new int[nums.length + 1];

        for (int i = 1; i <= nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }

        for (int i = 0; i < prefixSum.length; i++) {
            int end = binarySearchEnd(prefixSum, i, prefixSum[i] + target);
            if (end != -1) {
                minLength = Math.min(minLength, end - i);
            }
        }

        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    private int binarySearchEnd(int[] prefixSum, int start, int target) {
        int left = start;
        int right = prefixSum.length - 1;
        int end = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid] >= target) {
                end = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return end;
    }
}

这个题目涉及到以下知识点

1. 前缀和数组
2. 滑动窗口思想
3. 二分搜索
4. 数组遍历
5. 条件判断和更新

代码的文字解释如下：

• target 是目标战斗力值，nums 是战斗力数组。
• 创建前缀和数组 prefixSum，其中 prefixSum[i] 表示从数组开头到第 i-1 个元素的累积和。
• 使用循环计算前缀和数组。
• 对每个位置 i，使用二分搜索找到在 [i, n] 范围内，累积和大于等于 prefixSum[i] + target 的最小位置 end。这个位置 end 可以表示满足条件的连续牛群的结束位置。
• 如果找到了这样的 end，更新最小长度 minLength，即最短连续牛群的长度。
• 返回最短连续牛群的长度。如果没有满足条件的连续牛群，则返回0。