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

网站做的最好的网站有哪些百度号码认证平台首页

网站做的最好的网站有哪些,百度号码认证平台首页,网页设计图片切换怎么做,建设部网站房地产资质209. 长度最小的子数组 力扣题目链接(opens new window) 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。 示例: 输入…

209. 长度最小的子数组

力扣题目链接(opens new window)

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。

示例:

输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。

提示:

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

思路

滑动窗口

滑动窗口:不断的调整子序列的起始位置和终止位置,从而得到想要的结果。

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

那么滑动窗口如何用一个for循环来完成这个操作呢?
只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。

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

  • 窗口内是什么?
    窗口就是满足其和 ≥ s 的长度最小的连续子数组。
  • 如何移动窗口的起始位置?
    窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。
  • 如何移动窗口的结束位置?
    窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。

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

leetcode_209

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

class Solution {//方法:滑动窗口public int minSubArrayLen(int target, int[] nums) {int left = 0;//滑动窗口起始位置int sum = 0; //滑动窗口数值之和//结果取整型类型的最大值,便于和遍历的结果比较     int result = Integer.MAX_VALUE;for(int right = 0; right < nums.length; right++){sum += nums[right]; //使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件while(sum >= target){//right - left + 1为子序列(滑动窗口)的长度result = Math.min(result, right - left + 1); sum -= nums[left++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)}}// 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列return result == Integer.MAX_VALUE ? 0 : result;}
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
http://www.fp688.cn/news/146096.html

相关文章:

  • 贵州省职业技能学历双提升工程seo专业培训机构
  • 重庆建设厅的网站首页免费网站搭建
  • 如何制作一个公司网站web网页制作成品
  • 做网站建设公司哪家好关联词有哪些小学
  • 做平台网站怎么做怎么样建网站
  • cc网站域名注册郑州百度seo网站优化
  • 如何写网站建设方案关键词排名提升工具
  • 应用网站制作免费网站或软件
  • 武汉市文明城市建设网站网站流量查询服务平台
  • 网站做很多关键词淘宝流量网站
  • 日照比较好的网站建设企业crm软件
  • 深圳高端网站建设介绍产品的营销推文
  • 网站开发者模式下载视频网络推广视频
  • 网站建设目标冯耀宗seo视频教程
  • wordpress适合网站seo优化方案设计
  • 动态网站开发工具类似互推商盟的推广平台
  • 查看网站模板中文搜索引擎有哪些平台
  • 沈阳想做网站各大网站的网址
  • 草编网站建设方案哪个搜索引擎最好用
  • 中山营销网站建设联系方式站长之家seo综合查询
  • jquery加速wordpress网站seo课设
  • 绍兴网站制作公司河北seo基础
  • 青岛海川建设集团有限公司网站营销策划与运营团队
  • 西安商城网站建设制作聚合搜索引擎入口
  • 外贸网站该怎么做热门搜索
  • 西安医院网站建设最新做做网站
  • ssp媒体服怎样做网站曼联官方发文
  • 做网站收入怎样网络营销方法有哪些?
  • 企业网站写好如何发布北京本地网络推广平台
  • 接给别人做网站的活有没有专门做营销的公司