Leetcode 209：Minimum Size Subarray Sum

2023-10-10 11:28:34

Leetcode 209： Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

说人话：

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

几个要点：

  • 非负
  • 连续子数组
  • 返回的是长度
  • 可能无解

举例：

Leetcode 209：Minimum Size Subarray Sum

[法1] 暴力法

思路

暴力法的思路非常简单：

  • 求出 nums 的所有子数组
  • 找到哪些子数组元素之和 >= s
  • 找到长度最短的那个子数组
代码
class Solution {

    public int minSubArrayLen(int s, int[] nums) {
				
      	//子数组长度，这里默认为 nums.length+1，最后如果还是它，则说明没有满足条件的子数组
        int length = nums.length+1;
				
      	//计算所有子数组的和，第一维记录和，第二维记录数组长度
        int[][] subArrayItemSum = getSubArrayItemSum(nums);

        if(subArrayItemSum == null){
            return 0;
        }

      	//找到符合条件的最短子数组
        for(int i=0; i<subArrayItemSum.length;i++){
            if(subArrayItemSum[i][0] >=s){
                if(subArrayItemSum[i][1] < length){
                    length = subArrayItemSum[i][1];
                }
            }
        }
        return length==(nums.length+1)?0:length;
    }


    //计算所有子数组的和，第一维记录和，第二维记录数组长度
    public int[][] getSubArrayItemSum(int[] nums){

        if(nums.length <= 0){
            return null;
        }

        //连续子数组总个数为 (1+n)n/2
        int[][] result = new int[nums.length*(nums.length+1)/2][2];
				
      	//子数组索引
        int index = 0;

        //(i+1) 代表子数组长度
        for(int i=0;i<nums.length;i++){

            //子数组[head....tail]
            int head = 0;
            int tail = i;
						
          	//滑动
            while(tail<nums.length){
                int sum=0;
                for(int k=head;k<=tail;k++){
                    sum += nums[k];
                }
                result[index][0] = sum;  //记录和
                result[index][1] = i+1;  //记录长度
              	//向右移动
                head++;
                tail++;
                index++;
            }
        }
        return result;
    }
}
提交结果
Leetcode 209：Minimum Size Subarray Sum
代码分析
  • 时间复杂度：O(n*((1+n)*n/2)) =O(n3)
  • 空间复杂度：O(2n) = O(n)
改进思路

很显然该做法的不可取的，时间复杂度和空间复杂度都太大了。我们先来优化暴力解法。首先第一个思路肯定是优化空间复杂度：不要分成两个方法，把两个方法合并为1，不借助 int[][] [][] 的额外空间。

[法2] 优化暴力算法的空间复杂度

思路

不要分成两个方法，把两个方法合并为1，不借助 int[][] [][] 的额外空间。

代码
class Solution {

    public int minSubArrayLen(int s, int[] nums) {
      
        if(nums.length <= 0){
            return 0;
        }

        //子数组长度，这里默认为 nums.length+1，最后如果还是它，则说明没有满足条件的子数组
        int length = nums.length+1;

        //(i+1) 代表子数组长度
        for(int i=0;i<nums.length;i++){

            //子数组[head....tail]
            int head = 0;
            int tail = i;
						
          	//滑动
            while(tail<nums.length){
                int sum=0;
                for(int k=head;k<=tail;k++){
                    sum += nums[k];
                }
              	//判断子数组是否满足条件
                if(sum >= s){
                  	//找长度最小的
                    if(i+1<length){
                        length = i+1;
                    }
                }
              	//右移
                head++;
                tail++;
            }
        }
        return length==(nums.length+1)?0:length;
    }
}
提交结果
Leetcode 209：Minimum Size Subarray Sum
代码分析
  • 时间复杂度：一样是 O(n3)
  • 空间复杂度：这次没借助其他的辅助空间，所以是 O(1)
改进思路

本次改进我们优化了空间复杂度，但是时间复杂度还是太大了。

[法3] 优化暴力算法的时间复杂度

思路

前面的算法中我们没有利用各个子数组直接的关系，导致做了非常多的重复运算。

事实上，如果我们用 sums[i] 来表示 nums[0…i-1] 的和（之所以是 i-1 是因为我们需要将 sums[0] 设置为0，方便后面做差运算的时候不遗漏元素），那么就存在一个规律：sums[j+1] - sums[i] = nums[i....j] 的和（其中 j = i+k），这个规律是可以帮助我们减少非常多的重复运算的。

总体思路：

  • 先记录下 sums[0…i] 的值
  • 利用 sums[r+1] - sums[l] 来得到 sums[l…r] 的值，其中 r = l + k
  • 记录最短的连续子数组长度并返回
代码
class Solution {

    public int minSubArrayLen(int s, int[] nums) {

        int result = nums.length + 1;

        int[] sums = new int[nums.length+1];
        //总长度是 nums.length+1，sums 第一个设为0
        sums[0] = 0;

        //sums[i] 记录 nums[0...i-1] 的和
        for(int i=1;i<nums.length+1;i++){
            sums[i] = sums[i-1] + nums[i-1];
        }

        for(int i=0;i<nums.length;i++){
            for(int j=i;j<nums.length;j++){
                //使用 sums[j+1] - sums[i] 快速获得 nums[i....j] 的和
                if((sums[j+1] - sums[i]) >= s){
                    result = (result < (j-i+1))?result:(j-i+1);
                }
            }
        }
        return (result==(nums.length+1))?0:result;
    }
}
提交结果
Leetcode 209：Minimum Size Subarray Sum
代码分析
  • 时间复杂度：O(n2)
  • 空间复杂度：O(n)
改进思路

经过两次优化，我们的代码已经符合 Leetcode 的要求了。但是暴力法中还是会有很多的重复运算，导致时间复杂度还是处于比较高的 O(n2)。

[法4] 滑动窗口

思路
Leetcode 209：Minimum Size Subarray Sum

滑动窗口的思想是我们取 2 个索引 i 和 j ，这样就围成了一个窗口，我们可以计算这个窗口中 nums[i…j] 的和：

  • ① 如果 nums[i…j] 的和 < s，那么就意味着需要更多的元素，那么我们就让 j++，放入更多的元素，直至 nums[i…j] 的和 >=s，记下这个连续子数组的长度；

    Leetcode 209：Minimum Size Subarray Sum

  • ② 如果我们的元素足够多的话，也就是 nums[i…j] 的和已经满足 >=s 了，那么我们就从头开始减少元素，也就是 i++。直至 nums[i…j] 的和已经不能满足 >=s 了，我们就记录下能满足 nums[i…j] 的和>=s 连续子数组的长度，跟之前的长度进行比较，选取小的。

    Leetcode 209：Minimum Size Subarray Sum

  • 然后我们再继续循环 ① 和 ②，直至遍历完整个数组。

代码
class Solution {

    public int minSubArrayLen(int s, int[] nums) {

        int result = nums.length + 1;

        //总长度是 nums.length+1，sums 第一个设为0,作为冗余项，避免作差运算的时候漏元素
        int[] sums = new int[nums.length+1];
        sums[0] = 0;

        //sums[i] 记录 nums[0...i-1] 的和
        for(int i=1;i<nums.length+1;i++){
            sums[i] = sums[i-1] + nums[i-1];
        }

        int left=0;  //窗口左边界
        int right=0; //窗口右边界

        //滑动窗口
        while(right < nums.length && left<= nums.length){
            //nums[right...left]已经满足 >=s
            if((sums[right+1] - sums[left]) >= s){
                result = (result < (right-left+1))?result:(right-left+1);
                //缩小左窗口，寻找更短的连续子数组
                left++;
            }
            //nums[right...left]已经不满足 >=s
            else{
                //增大右窗口，寻找满足条件的连续子数组
                right++;
            }
        }

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

    }
}
提交结果
Leetcode 209：Minimum Size Subarray Sum
代码分析
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
改进思路

目前我们已经成功实现将时间复杂度优化到 O(n) 这样一个比较合理的大小了，但是此时我们的空间复杂度还是处于 O(n) 这样一个比较大的规模，接下来就来想办法怎么样不用 sums[] 这个辅助空间来完成我们的寻找任务。

[法5] 优化滑动窗口

思路

要抛弃使用 sums[] 这个辅助空间的话，那么我们可以直接使用一个 sum 变量，通过添加或减少左右窗口来动态变化窗口范围内元素的和。

代码
class Solution {

    public int minSubArrayLen(int s, int[] nums) {

        int result = nums.length + 1;
        int sum = 0; //总和

        //窗口[left....right]
        int left = 0;   //窗口左边界
        int right = -1; //窗口右边界

        //滑动窗口
        while(left < nums.length){

            //nums[left...right] 的和还不满足，那就继续从右边加元素
            if( sum < s && (right+1 < nums.length)){
                right++;
                sum += nums[right];
            }
            //nums[left...right] 的和已经满足条件，从左边缩小窗口，企图找到更小的连续子数组
            else{
                sum -= nums[left];
                left++;
            }

            //记下满足条件的连续子数组的最短长度
            if(sum >= s){
                result = (result<(right-left+1))?result:(right-left+1);
            }
        }
        return (result==nums.length+1)?0:result;
    }
}
提交结果
Leetcode 209：Minimum Size Subarray Sum
代码分析
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
改进思路

上面我们每滑动一次就重新判断是否需要更新 result 的值，还是比较繁琐的。

其实我们可以在不满足条件的时候一直往右边加元素，直至满足条件，然后判断是否需要更新 result 的值；

然后在满足条件的时候一直减少左边的元素，直到不满足条件，然后根据最后一次满足条件的窗口长度来判断是否需要更新 result 的值。

[法6] 再次优化滑动窗口

思路
  • 在不满足条件的时候一直往右边加元素，直至满足条件，然后判断是否需要更新 result 的值；
  • 在满足条件的时候一直减少左边的元素，直到不满足条件，然后根据最后一次满足条件的窗口长度来判断是否需要更新 result 的值。
代码
class Solution {

    public int minSubArrayLen(int s, int[] nums) {

        int result = nums.length + 1;
    
        int sum = 0; //总和

        //窗口[left....right]
        int left = 0;   //窗口左边界
        int right = -1; //窗口右边界

        //滑动窗口
        while(right+1 < nums.length){
            //不满足就一直加元素
            while( right+1 < nums.length && sum < s){
                right++;
                sum += nums[right];
            }

            //不加元素了，要么是没元素可以加了，要么是已经加够了
            if(sum >= s){
                result = (result<(right-left+1))?result:(right-left+1);
            }

            boolean hasDelete = false;
            //满足条件的话就一直从左边删元素
            while(left < nums.length && sum >= s){
                hasDelete = true;
                sum -= nums[left];
                left ++;
            }
            //有进行删除操作然后跳出来，说明最后一次删除之前是满足条件的
            if(hasDelete){
                result = (result<(right-(left-1)+1))?result:(right-(left-1)+1);
            }
            
        }

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

    }
}
提交结果
Leetcode 209：Minimum Size Subarray Sum
代码分析
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
上一篇：小白Leetcode初体验


下一篇：vue elment.style样式修改（第三方组件自生成元素）