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

长度最小的子数组

时间:2024-08-14 17:38:26浏览次数:12  
标签:tmp target min 最小 value len 数组 长度

**问题**

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

 

**注意问题**

子数组的定义:一个或连续多个数组中的元素组成一个子数组(子数组最少包含一个元素),  注意这个连续。

 

**解决方法**

解决方法可以分为两种,第一种是暴力破解法,也是最直观的方法,第二种是滑动窗口的方法

 

**暴力破解法**

 

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 初始 将min_value 设置为无穷大
        min_value=float('inf')
        flag=0

        input_len=len(nums)

        for i in range(input_len):
            tmp_value=0
            for j in range(i,input_len):
                # 进行嵌套的遍历 因为找的是子数组 具有连续性
                tmp_value+=nums[j]
                # 如果大于target,就和min_value进行比较,选择最小的
                if tmp_value>=target:
                    min_value=min(min_value,j-i+1)
                    flag=1
                    # 如果值大于target 就结束改循环
                    break
        
        if flag:
            return min_value
        else:
            return 0
                

但是上述的解决方法的时间复杂度在N 方,怎么优化这个暴力破解法呢,我们采用滑动窗口,变动右指针,如果当前的累加值是大于目标值,那就移动左指针,找最小的子数组,代码如下:

 

**滑动窗口法**

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 初始 将min_value 设置为无穷大
        min_value=float('inf')
        left=0

        num_len=len(nums)
        tmp_value=0
        # 一直往右走
        for j in range(num_len):

            tmp_value+=nums[j]

            while tmp_value>=target:

                min_value=min(min_value,j-left+1)
                # 往左边滑动,来找最小的子数组
                tmp_value-=nums[left]
                left+=1

        return min_value if min_value!=float('inf') else 0

 

标签:tmp,target,min,最小,value,len,数组,长度
From: https://www.cnblogs.com/TW-NLP/p/18359450

相关文章

  • 如何定义和引用二维数组
    一.二维数组常称为矩阵,把二维数组写成行和列的排列形式。、二.怎么定义二维数组floatpay[3][5];以上定义了一个float型的二维数组,第1维有3个元素,第2维有6个元素。每一维的长度分别用一对方括号括起来。二维数组定义的一般形式为  类型说明符数组名【常量表达式】【......
  • 三:指针在数组中的应用
    1.使用指针访问数组指针的加减运算可以用来在内存中移动指针的地址。加上一个整数`n`,实际上就是移动了`n`个步长字节。步长是由指针指向的数据类型决定的。例如,假设有一个`int`类型的指针`p`:int*p=(int*)100;那么,执行`p+1`后,指针地址会向后移动`sizeof(in......
  • 【代码随想录】一、数组:3.双指针 - 977.有序数组的平方
    本文为977.有序数组的平方的解法,部分图文参考自代码随想录977.有序数组的平方。1.题目1:977.有序数组的平方1.1.解法1:直接排序classSolution{public:vector<int>sortedSquares(vector<int>&nums){for(inti=0;i<nums.size();i++){n......
  • 【代码随想录】一、数组:2.移除元素
    部分图文参考于:代码随想录-移除元素和力扣官方解法。1.题目1★:27.移除元素1.1.解法1:暴力解法考验对数组底层实现的理解:数组的元素是不能删的,只能覆盖。通过两层for循环来求解,外层for循环遍历数组元素,内层for循环将目标值进行覆盖。classSolution{public:intremove......
  • 【代码随想录】一、数组:1.二分查找
    部分图文参考于:代码随想录-二分查找,本文仅作为个人学习使用,如有侵权,请联系删除。1.概念二分查找也称折半查找(BinarySearch),是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知,运用二分搜索的前提是数组必须是有序的,这里需要注意的是,我们的输入不一定是数组,也......
  • 【代码随想录】一、数组:理论基础
    原文链接:代码随想录-数组理论基础,本文仅作为个人学习使用,如有侵权,请联系删除。数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力。数组是存放在连续内存空间上的相同类型数据的集合。数组可以方便的通过下标索引的方式获取到下......
  • c语言转换char字符数组为大写小写
    #include<string.h>#include<stdlib.h>#include<stdio.h>#include<time.h>#include<ctype.h>#include<sys/stat.h>voidgetdate(char*datestr,char*format){ time_tnnowtime=time(NULL); structtm*ptmTemp=loc......
  • 2024“钉耙编程”中国大学生算法设计超级联赛(8)1006 cats 的最小生成树
    题目大意:给出有\(n\)个点\(m\)条边的图,接下来进行若干次操作,每次操作取出当前图的最小生成树,然后删去这些构成最小生成树的边,知道该图不连通,输出每条边在第几次操作时被删除思路:由于构成最小生成树的边数是\(n-1\)条边,所以最多操作次数为\(\lfloor\frac{m}{n-1}\rfloor\),每次......
  • 2024-08-14:用go语言,给定两个长度分别为n和m的整数数组nums和changeIndices,下标从1开始
    2024-08-14:用go语言,给定两个长度分别为n和m的整数数组nums和changeIndices,下标从1开始。初始时,nums中所有下标均未标记。从第1秒到第m秒,每秒可以选择以下四种操作之一:1.选择范围[1,n]中一个下标i,将nums[i]减少1。2.将nums[changeIndices[s]]设为任意非负整数。3.选择范围......
  • 从字符串里面解析数组
    需求,从一个字符串里面,解析出一个数组。例如:“1,2,3,4,5”,"1-5","1,2,4","5-10,12,13"能正常解析出一个数组出来。字符串里面,支持“,”,"-"2种用法。 #include<iostream>#include<string>#include<vector>#include<sstream>#......