首页 > 其他分享 >LeetCode 209.长度最小的子数组

LeetCode 209.长度最小的子数组

时间:2024-06-23 18:31:19浏览次数:25  
标签:right 窗口 target nums 209 sum 数组 LeetCode left

链接

209. 长度最小的子数组 - 力扣(LeetCode)

题目

给定一个含有 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

思路1: 暴力解法。遍历枚举出所有的组合,然后判断。 时间复杂度为O(N!)。 显然是不可取的

思路2:滑动窗口思想。 用 left 和 right 指针维护一段窗口,并用sum记录该窗口中的数据的和。由于该题中数据都为正整数,那么当窗口中数据个数增多,那么该窗口内的数据之和也会增大。 当 窗口内数据之和<target时,right向后移动,使数据进入窗口。 当 窗口内数据之和>=target时,使left向后移动,从而使前面的数据出窗口。如下图。

为什么 当 窗口内数据之和>=target时,使left向后移动即可? 

原因: 该题中数据都为 正整数,因此 当 窗口数据之和 >= target 时, 在left当前位置,right继续向后是毫无意义的,因为right向后移动,那么窗口之和会增加,仍旧是>=target的,但窗口长度会增大。题目要求是寻找符合>=target的最小子数组,即符合>=target且窗口长度最小的情况。因此 应该 以当前left位置的数据值得遍历的已经遍历完全了,left应该向后移动,来遍历下一个位置的情况。而left++后,right也无需回退,只需要更新sum的值,将退出窗口的数据的值减去,即可得到现在窗口的维护的数据的数据之和,即sum -= nums[原位置的left];

代码:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0 , right = 0;
        int sum = 0; 
        int len = 0;
        while(right < nums.size())
        {
            sum += nums[right];//更新 窗口的数据和
            while(sum >= target)
            {
                //更新最短的子数组的长度len
                if(len == 0) len = (right - left + 1);
                else len = (right - left + 1) < len ? (right -left + 1) : len;
                //更新sum
                sum -= nums[left];
                //出窗口
                left++;
            }
            //进窗口
            right++;
        }
        return len;
    }
};

标签:right,窗口,target,nums,209,sum,数组,LeetCode,left
From: https://blog.csdn.net/2301_78913125/article/details/139890923

相关文章

  • Leetcode84 柱状图中最大的矩形
    题目描述给定n个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为1。求在该柱状图中,能够勾勒出来的矩形的最大面积解题思路思路一:暴力寻找,从每个位置出发,向左右两边扩散查找,若发现柱形比当前位置高,则宽度加一,组成长方形,代码实现如下,但是提交之后......
  • 12-数组
    数组的概述相同类型数据的有序集合按照一定的先后次序排序组合而成每个数组元素可以通过一个下标来访问它们数组一旦被创建,它的大小就不可改变数组中的元素可以是任何数据类型,包括基本类型和引用类型数组变量属于引用类型,数组也可以看成是对象,数组中的每个元素相当于该对象......
  • NumPy数组的分割
    NumPy数组的分割方法说明split()分割数组hsplit()沿横轴分割数组vsplit()沿纵轴分割数组1.split()np.split(arr,整数或数组,axis=n)(1)整数importnumpyasnparr=np.arange(10)res=np.split(arr,5)print("arr:")print(arr)print("res:")p......
  • LeetCode 448. 找到所有数组中消失的数字(哈希表)
    448.找到所有数组中消失的数字思路:方法一,借助额外的0(n)空间sta进行哈希classSolution{public:vector<int>findDisappearedNumbers(vector<int>&nums){intn=nums.size();vector<int>sta(n,0);for(inti=0;i<n;i++){......
  • 数组元素的数量
    在数组初始化时,我们不希望将数组大小写死,后续可能会有修改,那么对于未指定大小的数组,如何计算其元素个数?思路:已知数组名代表整个数组的物理大小,数组内单个元素代表数组的一个单元物理大小,假设数组物理空间是100,单个元素物理空间是5,那么该数组一共有20个元素。array_element_numbe......
  • 力扣-1630. 等差子数组
    1.题目介绍题目地址(1630.等差子数组-力扣(LeetCode))https://leetcode.cn/problems/arithmetic-subarrays/题目描述如果一个数列由至少两个元素组成,且每两个连续元素之间的差值都相同,那么这个序列就是等差数列。更正式地,数列s是等差数列,只需要满足:对于每个有效的i,s[i......
  • 647. 回文子串(leetcode)
    647.回文子串(leetcode)题目描述给你一个字符串s,请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。示例1输入:s=“abc”输出:3解释:三个回文子串:“a”,“b”,“c”......
  • LeetCode665.非递减数列
    LeetCode刷题记录文章目录......
  • 152. 乘积最大子数组
    152.乘积最大子数组题目链接:152.乘积最大子数组代码如下:classSolution{public:intmaxProduct(vector<int>&nums){intres=nums[0];vector<int>f(nums.size()+1,0),g(nums.size()+1,0);f[0]=nums[0],g[0]=nums[0];......
  • Leetcode 力扣 125. 验证回文串 (抖音号:708231408)
    如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。字母和数字都属于字母数字字符。给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false 。示例1:输入:s="Aman,aplan,......