当前位置: 首页 > news >正文

济南微信网站做网站的心得

济南微信网站,做网站的心得,应用公园app在线制作,深圳出行最新通告目录 0.滑动窗口原理讲解1.长度最小的子数组1.题目链接2.算法原理讲解3.代码实现 0.滑动窗口原理讲解 滑动窗口:“同向双指针”滑动窗口可处理「⼀段连续的区间」问题如何使用? left 0, right 0进窗口判断 是否出窗口 更新结果 -> 视情况而定 可能…

目录

  • 0.滑动窗口原理讲解
  • 1.长度最小的子数组
    • 1.题目链接
    • 2.算法原理讲解
    • 3.代码实现


0.滑动窗口原理讲解

  • 滑动窗口:“同向双指针”
  • 滑动窗口可处理「⼀段连续的区间」问题
  • 如何使用?
    1. left = 0, right = 0
    2. 进窗口
    3. 判断
      • 是否出窗口
    4. 更新结果 -> 视情况而定
      • 可能在出窗口前
      • 可能在进窗口之后
  • 具体原理解析将结合**「长度最小的子数组」**来说明

1.长度最小的子数组

1.题目链接

  • 长度最小的子数组

2.算法原理讲解

  • 此问题分析的对象是**「⼀段连续的区间」,因此可以考虑「滑动窗⼝」**的思想来解决

  • 让滑动窗⼝满⾜

    • i位置开始,窗⼝内所有元素的和⼩于target
    • 当窗⼝内元素之和第⼀次⼤于等于⽬标值的时候,就是i位置开始满⾜条件的最⼩⻓度
  • 做法:

    • 如果窗⼝sum >= target
      • 更新结果,并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果
        • 因为左端元素可能很⼩,划出去之后依旧满⾜条件
    • 如果窗⼝sum不满⾜条件:
      • right++,让下⼀个元素进⼊窗⼝
        请添加图片描述
  • 为何滑动窗⼝可以解决问题,并且时间复杂度更低?

    • 这个窗⼝寻找的是:以当前窗⼝最左侧元素(记为left1)为基准,符合条件的情况
      • 即:从left1开始,满⾜sum >= target时的最右侧(记为right1)能到哪⾥
    • 既然已经找到从left1开始的最优的区间,那么就可以⼤胆舍去left1
      • 但是如果继续像暴力求解⽅法⼀样,重新开始统计第⼆个元素(left2)往后的和,势必会有⼤量重复的计算
        • 因为在求第⼀段区间的时候,已经算出很多元素的和了,这些和是可以在计算下次区间和的时候⽤上的
    • 此时,rigth1的作⽤就体现出来了,只需将left1这个值从sum中剔除
      • right1这个元素开始,往后找满⾜left2元素的区间
        • 此时right1也有可能是满⾜的,因为left1可能很⼩,sum剔除掉left1之后,依旧满⾜⼤于等于 target
    • 这样就能省掉⼤量重复的计算
    • 总结:利用单调性,规避了很多没有必要的枚举行为
      • 此处的单调指滑动窗口内sum的单调性,而不是数组原始数据的单调性
  • 时间复杂度 O ( N ) O(N) O(N)

    • 虽然代码是两层循环,但是left指针和right指针都是不回退的,两者最多都往后移动n

3.代码实现

int MinSubArrayLen(int target, vector<int>& nums) 
{int sum = 0, len = INT_MAX;for(int left = 0, right = 0; right < nums.size(); right++){sum += nums[right]; // 进窗口while(sum >= target) // 判断{len = min(len, right - left + 1); // 更新结果sum -= nums[left++]; // 出窗口}}return len == INT_MAX ? 0 : len;
}
http://www.yayakq.cn/news/631892/

相关文章:

  • 交易网站建设需要学什么wordpress页面移动端
  • 做网站定金是多少钱大连网站制作怎么做
  • 企业站模板明细如何做cad的模板下载网站
  • 温州网站优化指导wordpress登陆评论
  • 国外产品设计网站推荐网站建设策
  • 手机怎样建网站网站2019建设目标
  • 单页网站建设一般收费个人工作室营业执照
  • 安卓app做网站外壳网站集约化建设启示和建议
  • 公司注册信息查询系统网站建设和网络优化的区别
  • 网站设计原型图怎么做安阳市地图
  • 建设论坛网站大全河北省城乡住房和建设厅网站
  • 广东专业企业网站建设就要使用网页制作工具
  • 建网站找哪家海南建设大厅网站
  • 免费模型网站哪里可以做网站推广
  • 武义县建设局网站网站建设方案书的内容管理制度
  • 工业网站开发商亚马逊amz123
  • 灯具网站怎么做做H5哪个网站字体漂亮一些
  • 打开网站总显示建设中wordpress实时推送 php
  • 福州建设银行官网招聘网站网络公司做的网站被告图片侵权
  • 麻涌建设网站东莞最新消息今天
  • 网站统计访客数量怎么做项目四网站建设实训报告
  • 襄阳手机网站建设公司wordpress标题设置
  • 淘宝做网站的店怎么做同学录的网站
  • 企业做网站公司排名口碑北京外贸营销网站建设费用
  • 厦门网站设计个人网站设计说明
  • 有品质的网站推广公司上海最出名的编程培训
  • 贵州 网站建设学历提升机构哪家好
  • 数学老师做直播的网站网站开发需求文件
  • 电子商务网站的建设费用传智ui设计培训
  • 做行业网站投资多少如何开展网络营销