滑动窗口-＞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.带内存缓冲区的字符流：BufferedReader

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

原文地址：https://blog.csdn.net/robin_suli/article/details/142654316

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！