首页 > 其他分享 >209.长度最小的子数组——学习笔记

209.长度最小的子数组——学习笔记

时间:2023-03-20 21:36:20浏览次数:71  
标签:right target nums 209 笔记 int result 数组

题目:给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

示例 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 <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

题目来源:力扣(LeetCode)链接

题解

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int sum = 0; //sum用来存放子串的和
        int subLength = 0; //subLength存放子串的长度
        int result = Integer.MAX_VALUE; //result存放最后的结果
        int left = 0; //窗口的左索引
        int right = 0; //窗口的右索引
        for (; right < len; right++) {
            // 扩展窗口,直到和满足要求
            sum += nums[right];
            while (sum >= target) {
                subLength = right - left + 1;//数组下标从0开始,所以要+1
                //result与子串长度比较,取最小值
                result = result > subLength ? subLength : result;
                //收缩窗口,直到和不满足要求,继续扩展窗口
                sum -= nums[left];
                left++;
            }
        }
        //如果result==Integer.MAX_VALUE,说明不存在满足要求的子串,返回0
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

标签:right,target,nums,209,笔记,int,result,数组
From: https://www.cnblogs.com/benben-home/p/17228262.html

相关文章

  • 算法笔记的笔记——第4章 算法初步
    排序选择排序(简单选择排序)从1到n进行n趟操作每趟从待排序部分(i到n)选择最小元素与待排序部分第一个元素(i)交换复杂度O(n2)for(inti=0;i<n;i++){ intk=i;......
  • 剑指Offer 29.顺时针打印矩阵——学习笔记
    题目:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。示例1:输入:matrix=[[1,2,3],[4,5,6],[7,8,9]]输出:[1,2,3,6,9,8,7,4,5]示例2:输入:matrix=[[1......
  • 54.螺旋矩阵——学习笔记
    题目:给你一个m行n列的矩阵matrix,请按照顺时针螺旋顺序,返回矩阵中的所有元素。示例1:输入:matrix=[[1,2,3],[4,5,6],[7,8,9]]输出:[1,2,3,6,9,8,7,4,5]示例2......
  • 59.螺旋矩阵II——学习笔记
    题目:给你一个正整数n,生成一个包含1到n2所有元素,且元素按顺时针顺序螺旋排列的nxn正方形矩阵matrix。示例1:输入:n=3输出:[[1,2,3],[8,9,4],[7,6,5]]示例......
  • 76.最小覆盖子串——学习笔记
    题目:给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串,则返回空字符串""。注意:对于t中重复字符,我们......
  • 算法笔记的笔记——第5章 数学问题
    简单数学略最大公约数与最小公倍数最大公约数intgcd(inta,intb){if(b==0){returna;}else{returngcd(b,a%b);}}......
  • 外设驱动库开发笔记52:PM3003S激光粉尘仪驱动
      空气质量是现代日常生活中人们所关注的事情,也是生存环境好坏的一种体现。其中粉尘数量监测更是空气质量检测中最常见的对象,在我们的检测设备中也经常会有这种需求。检......
  • 数组理论基础
    数组理论基础数组是存放在连续内存空间上的相同类型数据的集合。数组下标都是从0开始的。数组的元素是不能删的,只能覆盖。Java的二维数组的每一行头结点的地址是没有......
  • 704.二分查找——学习笔记
    题目:给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。示例1输入:nums=[-1,0,3......
  • 35.搜索插入位置——学习笔记
    题目:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(logn)的算法。......