关于java:LeetCode209长度最小的子数组

3次阅读

共计 1303 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：给定一个含有 n 个正整数的数组和一个正整数 target。

找出该数组中满足其和 ≥ target 的长度最小的间断子数组 [nums ~l~, nums~l+1~, …, nums~r-1~, nums~r~]，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：滑动窗口

首先，判断非凡状况，如果数组为空，间接返回 0。

否则，应用滑动窗口法来判断是否存在最小的间断子数组，具体解决逻辑如下：

首先，申明滑动窗口的左右边界，并用 minLen 记录最小的间断子数组的长度；

遍历数组，直到右边界遍历到原数组的最初一个数字地位；

计算以后范畴的间断子数组的和，判断以后的和是否比 target 小，如果不小于，则将窗口的左边界右移，并且判断以后的间断长度是否是最小的；如果小于，则将窗口的右边界右移。

最初，判断 minLen 是否已找到，如果不存在则返回 0；否则，返回 minLen。

public class LeetCode_209 {
    /**
     * 滑动窗口
     *
     * @param target 目标值
     * @param nums   原数组
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        // 如果数组为空，间接返回 0
        if (nums == null || nums.length == 0) {return 0;}
        // 记录最小的间断子数组的长度
        int minLen = Integer.MAX_VALUE;
        // 滑动窗口的左右边界
        int left = 0, right = 0;
        // 遍历直到右边界遍历到原数组的最初一个数字地位
        while (right < nums.length) {
            int sum = 0;
            // 计算以后范畴的间断子数组的和
            for (int i = left; i <= right; i++) {sum += nums[i];
            }
            // 判断以后的和是否比 target 小，如果不小于，则将窗口的左边界右移，并且判断以后的间断长度是否是最小的；如果小于，则将窗口的右边界右移
            if (sum >= target) {minLen = Math.min(minLen, right - left + 1);
                left++;
            } else {right++;}
        }

        if (minLen == Integer.MAX_VALUE) {return 0;}
        return minLen;
    }

    public static void main(String[] args) {
        // 测试用例一，冀望输入：2
        System.out.println(minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
        // 测试用例二，冀望输入：0
        System.out.println(minSubArrayLen(11, new int[]{1, 1, 1, 1, 1, 1, 1, 1}));
    }
}