滑动窗口-＞dd爱框框

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());}
}