同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如果有更好的方法,欢迎指点,共同进步~~

有其他语言代码也可在留言区留言,谢谢

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】


长度最小的子数组

  • 时间:2022-05-11
  • 题目序号:209
  • 难度:中等

问题描述

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

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

来源:力扣(LeetCode)

示例1

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

示例2

输入:target = 4, nums = [1,4,4]
输出:1

示例3

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

提示

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

题解部分参考自代码随想录。如有侵权,请联系进行删除~~
  • 在解题时,我们都可以先思考暴力解法进行解题,然后再通过逐步优化,来提高代码的性能
  • 对于本题,可以通过暴力和滑动窗口两种方法进行解决

暴力解法

  • 暴力解法一般都比较容易想得到,就是一一列举,使用穷举所有结果,筛选出符合要求的结果
  • 对于本题而言,暴力解法需要两层for循环(可以当作双指针来理解)
  • 对于外层循环i是(0~nums.length),内存循环j是(i~nums.length)
  • 需要设置result(最终结果)、subLength(子数组长度)、sum(子数组元素和)三个变量来完成本题
  • sum需要写在第一层循环(每次都需要初始化归0,不断更新)
  • subLength可由j - i + 1计算获得
  • result可以设置默认值为int的最大值,然后不断更新,获得满足题意的最短子数组长度。(最后返回时进行判断,如果没找到就返回0)
这里可以配合下方代码查看,会相对的好理解一些

滑动窗口

  • 滑动窗口主要就是通过对窗口的滑动,实现本题
  • 也是需要两个指针,暂且定为i、j(代码实现中用的left和right,更直观一些)

209.长度最小的子数组

  • 两指针同时指向0位置,然后j指针向后滑动,直到当前i、j确定的子数组满足题意(和大于target)
  • 当j滑动到满足题意的位置后,开始缩小窗口大小(尽可能取满足题意的最小子数组)
  • 缩小窗口大小就是给i++,进行缩小后,继续判断当前子数组是否满足题意,不满足继续将j指针向后滑动,直到满足题意位置
  • 重复上述步骤,不断更新result的值,直到i指向nums.length

  • 在每次缩小滑动窗口时,一定要注意给sum减去被滑出的元素值,并将i++
  • 上图中的三行代码就是精髓之处,需要好好理解。

注意: 上图三行代码的顺序不能改变

代码实现

通过上述分析,分别可以通过暴力解法和滑动窗口两种方式来实现本题目

暴力解法

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;     // 最终的结果
        int sum = 0;        // 子数组的和
        int subLength = 0;      // 子数组长度
        for(int i = 0; i < nums.length; i++){
            sum = 0;        // 初始化子数组元素和
            for(int j = i; j < nums.length; j++){
                sum += nums[j];     // 更新目前子数组和
                if(sum >= target){
                    subLength = j - i + 1;      // 更新子数组长度
                    result = result < subLength ? result : subLength;       // 更新最终结果
                    break;
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;       // 如果没找到,返回0
    }
}

时间复杂度:O(n^2)

空间复杂度:O(1)

滑动窗口

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;     // 最终的结果
        int sum = 0;        // 子数组的和
        int subLength = 0;      // 子数组长度
        int left = 0;
        for(int right = 0; right < nums.length; right++){
            sum += nums[right];
            while(sum >= target){
                subLength = right - left + 1;       // 更新子数组长度
                result = result < subLength ? result : subLength;   // 更新结果
                sum -= nums[left++];       // 关键步骤,缩小窗口范围
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;       // 如果没找到,返回0
    }
}

时间复杂度:O(n)

空间复杂度:O(1)

总结

  • 暴力解法依然比较好理解一些,就是穷举出所有可能的结果,筛选出符合题意的选项即可
  • 新接触到的滑动窗口,和双指针法有一些相似之处,但是滑动窗口更形象一些
  • 主要就是不断对窗口进行滑动,控制窗口的边界是十分重要的,需要理解滑动的规律
最后修改:2022 年 05 月 19 日
如果觉得我的文章对你有用,请随意赞赏