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

长度最小的子数组

时间:2022-09-01 20:12:10浏览次数:61  
标签:窗口 target nums 位置 最小 数组 滑动 长度

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

滑动窗口

接下来就开始介绍数组操作中另一个重要的方法:滑动窗口

所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果

在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环 完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢。

首先要思考 如果用一个for循环,那么应该表示 滑动窗口的起始位置,还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置,那么如何遍历剩下的终止位置?

此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。

那么问题来了, 滑动窗口的起始位置如何移动呢?

这里还是以题目中的示例来举例,s=7, 数组是 2,3,1,2,4,3,来看一下查找的过程:

209.长度最小的子数组

最后找到 4,3 是最短距离。

其实从动画中可以发现滑动窗口也可以理解为双指针法的一种!只不过这种解法更像是一个窗口的移动,所以叫做滑动窗口更适合一些。

在本题中实现滑动窗口,主要确定如下三点:

  • 窗口内是什么?
  • 如何移动窗口的起始位置?
  • 如何移动窗口的结束位置?

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。

窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。

解题的关键在于 窗口的起始位置如何移动,如图所示:

leetcode_209

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

package main

func minSubArrayLen(target int, nums []int) int {
   i:=0
   subLength:=0
   sum:=0
   result:=len(nums)+1
   for j:=0;j<len(nums);j++{
      sum+=nums[j]
      for sum>=target{
         subLength=j-i+1
         if result > subLength{
            result=subLength
         }
         sum=sum-nums[i]
         i++
      }
   }
   if result==len(nums)+1{
      return 0
   }else {
      return result
   }
}

标签:窗口,target,nums,位置,最小,数组,滑动,长度
From: https://www.cnblogs.com/suehoo/p/16647700.html

相关文章

  • 数组&指针
    分类inta;int*a;int**a;inta[10];int*a[10];int(*a)[10];//一个指向有10个整型数数组的指针int(*a)(int);//一个指向函数的指针,该函数有一......
  • java中的一维数组数组
    数组(array):是一种用于存储多个相同数据类型的存储模型(可以理解为容器)数组定义和静态初始化数组的两种定义格式:  格式1:    数据类型[]变量名;    范例......
  • C语言:变长数组(VLA)
    VLAC99新增了变长数组(variable-lengtharrayVLA),允许使用变量表示数组的维度。如下所示:intquarters=4;intregions=5;doublesales[regions][quarters];//......
  • 两个数的最小公倍数 与 最大公约数
    最小公倍数=两整数的乘积/最大公约数辗转相除法求最大公约数//3.辗转相除法(欧几里得算法)#include<stdio.h>intmain(){inta=0;intb=0;prin......
  • 日常开发记录-elementUI 文件上传假删除,防止删除文件后后悔的操作,无需调用后端删除文
    此篇博客关键是记录这种假删除的思想,后端给的删除接口也不一定非要用。。。上传文件假删除:<template><div><el-uploadclass="upload-demo"ac......
  • 如何在 Javascript 中清空数组?
    如何在Javascript中清空数组?在使用JavaScript编程时,程序员可能需要在许多情况下将数组设为空,一个非常常见的问题是如何清空数组并删除其所有元素!顺便说一句,这是最受......
  • C# 数组使用 For 循环改变颜色
    C#数组使用For循环改变颜色目标:用For循环改变颜色现在我们将ForEach循环更改为一个For循环,它与我们对ForEach循环所做的事情相同。所以,不同的是for循环......
  • js创建二维数组
    js创建二维数组的方法:方法一:直接设置letarr=[];arr[0]=[1,2,3,4,5,6];arr[1]=[10,20,30,40,50,60]方法二: fill+一个for循环letarr=newArray(1......
  • 高级开发人员知识:JavaScript 数组方法第 3 部分
    高级开发人员知识:JavaScript数组方法第3部分今天让我们来点高级的。这些数组方法总是遍历数组。基本上,您可以通过基本的for循环获得相同的功能。如果是这样,我们为什......
  • 获取数组元素
    这里有一个数组叫a1,数组内容为'red','green','yellow'。如果想直接获取'yellow',可通过他们的标号来获取,因为每一个值都是有标号的,从0开始,0,1,2,3……数组内容的标号......