LeetCode_58_MinimumSizeSubarraySum

LeetCode

发布日期: 2022-05-17

更新日期: 2022-05-17

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

1. question: 长度最小的子数组（中等）

给定一个含有 n 个正整数的数组和一个正整数 target 。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum

示例 1：

1
2
3

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1 2	输入：target = 4, nums = [1,4,4] 输出：1

示例 3：

1 2	输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0

提示：

1
2
3

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

2. answers

注意，这道题是在找子数组。即寻找起始下标和结束下标之间的长度。

本来我自己的思路是将数组全部求和，然后逐个减去数值较小的外围元素。但是这样做一方面，存在溢出的可能性；另一方面，一共19个测试用例，最后两个测试用例没有通过。所以先暂时放弃了这种想法。

首先采用暴力破解法做一下。起始下标从首元素开始向后遍历，终止下标从首元素开始向后遍历，组成子数组，直到子数组满足条件后终止下标不再继续遍历；并比较长度是否是最小值。之后，起始下标向后移动一位，重复上面的操作。

代码如下所示：

public class Solution_0056_02 {

    public static int minSubArrayLen(int target, int[] nums) {

        // 初始话为全部长度加1
        int result = nums.length + 1;
        int sums = 0;

        for (int i = 0; i < nums.length; i++) {

            sums = 0;

            for (int j = i; j < nums.length; j++) {

                sums += nums[j];

                // 满足条件，计算长度，并与前面的结果进行比较取最小值。退出此次循环。
                if(sums >= target) {
                    result = Math.min(result, j - i + 1);
                    break;
                }
            }

            // 以当前元素为起始位置的数组比较完毕，进行下个元素为起始位置。
        }

        // 此时，遍历结束，要么找到了结果；要么没有，那么result为初始默认值。
        return result == nums.length + 1 ? 0 : result;
    }

    public static void main(String[] args) {

        int[] nums = {2,3,1,2,4,3};
        int target = 7;

        System.out.println(minSubArrayLen(target, nums));
    }
}

但是暴力破解法的时间复杂度为O(n^2)。本质上说，多了很多无用的比较，实际上，当找到第一个子数组后，终止下标没必要再次和起始下标重合。只需要起始下标向前移动一位即可，因为如此时形成的新数组不满足条件，那么就相当于减少了一些比较，此时终止下标直接继续向后移动即可。如果满足条件，此时就相当于一个新的子数组，终止下标仍然不需要移动，即又减少了一些比较。起始下标继续移动，直到不满足条件时，终止下标向后移动。代码如下所示：

public class Solution_0056_02 {

    public static int minSubArrayLen(int target, int[] nums) {
        
        int result = nums.length + 1;

        int start = 0;
        int end = start;
        int sums = 0;

        while(end < nums.length) {

            sums += nums[end];

            // 如果满足条件，找到下一个子数组的起始下标
            // 注意，无论start怎么自加，也不会数组越界，因为当和end重合的时候，在进行这个操作就会变为0，肯定不满足条件退出循环。
            // 即最坏情况下，起始下标在终止下标的下一位。
            // 如果此时终止下标为数组的最后一位，那么此while循环结束后，则外层循环也就结束了。所以不存在数组下标越界的情况。
            while(sums >= target) {

                result = Math.min(result, end - start + 1);
                sums -= nums[start];
                start ++;
            }

            // 结束位置向后移动
            end ++;

        }

        return result == nums.length + 1 ? 0 : result;
    }

    public static void main(String[] args) {

        int[] nums = {2,3,1,2,4,3};
        int target = 7;

        System.out.println(minSubArrayLen(target, nums));
    }
}