1.题目:
2.题解:
2.1为什么用滑动窗口优化:
因为元素都是大于0的
所以:当找到大于等于x的值时,right可以不用返回
两个指针都往后走;因此可以使用滑动窗口优化暴力解法
2.2:滑动窗口具体使用步骤:
1.进窗口:sum += array[right];
2.判断:sum >= x 时出窗口
灵活更新结果(满足结果后)right-left+1<retlen
3.出窗口:sum -= array[left];
图解:
代码:这里注意使用了一个读取模板,不让Scanner输入会超时
import java.util.*; import java.io.*;public class Main {public static void main(String[] args) throws IOException {Read in = new Read();int n = in.nextInt(), x = in.nextInt();int[] array = new int[n+1];//注意下标从1开始for(int i = 1; i <= n; i++){array[i] = in.nextInt();}int left = 1;int right = 1;int sum = 0;int retlen = n;int retLeft = -1;int retRight = -1;while(right <= n){//进窗口sum += array[right];//判断while(sum >= x){//更新结果if(right-left+1 < retlen){retLeft = left;retRight = right;retlen = right-left+1;//更新以便于找出最小值}//出窗口sum -= array[left++]; }right++;}System.out.print(retLeft +" " +retRight);} }class Read // 自定义快速读入 {//字符串截取StringTokenizer st = new StringTokenizer("");//1.字节流->字符流:new InputStreamReader(System.in)//2.带内存缓冲区的字符流:BufferedReaderBufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException{while(!st.hasMoreTokens()){///读内存缓冲区里的一行数据:bf.readLine()st = new StringTokenizer(bf.readLine());}//获取每一个截取的字符串return st.nextToken();}//转化为自己想要的类型String nextLine() throws IOException{return bf.readLine();}int nextInt() throws IOException{return Integer.parseInt(next());}long nextLong() throws IOException{return Long.parseLong(next());}double nextDouble() throws IOException{return Double.parseDouble(next());} }
滑动窗口->dd爱框框
2024/10/25 13:14:34
来源:https://blog.csdn.net/robin_suli/article/details/142654316
浏览:
次
关键词:滑动窗口->dd爱框框
版权声明:
本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。
我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com
热文排行
- 《警世贤文》摘抄:处人篇、受恩篇、宽人篇、听劝篇、劝善篇(多读书、多看报、少吃零食多睡觉)
- nccl 03 记 回顾:从下载,编译到调试 nccl-test
- 【CVE-2024-38077】核弹级Windows RCE漏洞如何自检并修复该漏洞(附批量漏洞检测工具及分析伪代码)
- 【HW必备】用友NC-Cloud存在17处漏洞合集
- Vmess协议是什么意思? VLESS与VMess有什么区别?
- AD24设计步骤
- ctfshow-web入门-php特性(web132-web136)
- HarmonyOS应用开发者高级认证,Next版本发布后最新题库 - 单选题序号4
- windows11 ,ubuntu20.04双系统,ubuntu没有wifi的解决方式
- [python][whl]causal-conv1d的python模块在windows上whl文件下载
最新新闻
- 滑动窗口->dd爱框框
- Linux——redis
- 4、DDD、中台和微服务的关系
- Win10扩充C盘(把其他盘存储空间分给C盘)
- Qt/C++如何选择使用哪一种地图内核/不同地图的优缺点/百度高德腾讯地图/天地图/谷歌地图
- 今日指数项目项目集成RabbitMQ与CaffienCatch
- 用 Python 撸一个 Web 服务器-第4章:动态渲染数据
- 【保姆级】Python项目部署到Linux生产环境(uwsgi+python+flask+nginx服务器)
- 每日一练:二叉搜索树中第K小的元素
- 大模型中的检索增强RAG,Embedding,Index,Rerank,BGE,Faiss,chunking
推荐新闻
- 滑动窗口->dd爱框框
- Linux——redis
- 4、DDD、中台和微服务的关系
- Win10扩充C盘(把其他盘存储空间分给C盘)
- Qt/C++如何选择使用哪一种地图内核/不同地图的优缺点/百度高德腾讯地图/天地图/谷歌地图
- 今日指数项目项目集成RabbitMQ与CaffienCatch
- 用 Python 撸一个 Web 服务器-第4章:动态渲染数据
- 【保姆级】Python项目部署到Linux生产环境(uwsgi+python+flask+nginx服务器)
- 每日一练:二叉搜索树中第K小的元素
- 大模型中的检索增强RAG,Embedding,Index,Rerank,BGE,Faiss,chunking