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

【算法专题突破】滑动窗口 - 长度最小的子数组(9)

目录

1. 题目解析

2. 算法原理

3. 代码编写

写在最后:


1. 题目解析

题目链接:209. 长度最小的子数组 - 力扣(Leetcode)

 要注意的是,题目给的是正整数,

而题目要求并不难理解,就是找最短的子数组。

2. 算法原理

如果使用暴力的话,就是一个O(N3)的算法,复杂度很高,

我们可以用滑动窗口来做,滑动窗口是一个形象的名字,其实本质上也是一种双指针算法,

两个双指针同向移动,不回退,我们就将其称之为滑动窗口,因为就像窗口一样滑动。

那么我们怎么使用滑动窗口来做这道题呢?

1. 用两个指针作为窗口的左右边界

2. 进窗口

3. 判断如何出窗口

哪这道题来说:

两个指针 left 和 right 先初始化成0,

如果和小于目标值就让right++,

如果和大于等于目标值就记录结果,然后让 left++。 

3. 代码编写

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(), sum = 0, len = INT_MAX;int left = 0, right = 0;while(right < n) {sum += nums[right];while(sum >= target) {len = min(len, right - left + 1);sum -= nums[left++];}right++;}return len == INT_MAX ? 0 : len;}
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

http://www.lryc.cn/news/160584.html

相关文章:

  • 骨传导与入耳式耳机哪种音质好?该如何选择?
  • 【多线程】Timer任务定时器实现与盲等原子性问题的解决
  • SpringCloud-GetWay 路由网关
  • 使用生成式 AI 增强亚马逊云科技智能文档处理
  • 谈论浏览器内核
  • 电商卖家保障数据隐私和安全用什么安全的浏览器?
  • ECS通过DNAT将C非专线网段并网
  • g++模板显式实例化big file例子
  • Redis 删除策略
  • 自动化运维——ansible (五十二) (01)
  • 渗透测试漏洞原理之---【不安全的反序列化】
  • 建站系列(四)--- Web服务器之Apache、Nginx
  • TCP和UDP的区别
  • MBR、GPT、LVM分区
  • uniapp 下拉刷新
  • ifstream之seekg/tellg
  • OpenCV 01(图像加载与显示)
  • 1-Pytorch初始化张量和张量的类型
  • 诊断网络卡的原因
  • 100万级连接,爱奇艺WebSocket网关如何架构
  • 当电脑遇到msvcp110.dll丢失怎么办?最新解决方法分享
  • 微信小程序自动化测试pytest版工具使用方法
  • React 与 TS 结合使用时的技巧总结
  • 【深入解析spring cloud gateway】07 自定义异常返回报文
  • 如何写一个sh脚本将一个本地文件通过 scp命令上传到远程的 centos服务器?
  • 【CMake工具】工具CMake编译轻度使用(C/C++)
  • 用Navicat备份Mysql演示系统数据库的时候出:Too Many Connections
  • 知识储备--基础算法篇-矩阵
  • Zabbix -- QQ邮箱报警
  • eclipse链接MySQL数据库