滑动窗口经典例题

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

读入n，xn，xn，x,给出nnn个数a[1],a[2],……,a[n]a[1],a[2],……,a[n]a[1],a[2],……,a[n],求最小的区间[l,r][l,r][l,r]，使a[l]+a[l+1]+……+a[r]≥xa[l]+a[l+1]+……+a[r]≥xa[l]+a[l+1]+……+a[r]≥x，若存在相同长度区间，输出lll最小的那个

输入描述:

第一行两个数，n(1≤n≤10000000),x(1≤x≤10000)
第二行n个数a[i](1≤a[i]≤1000)

输出描述:

输出符合条件l,r(保证有解)

示例1

输入

复制10 20 1 1 6 10 9 3 3 5 3 7

10 20
1 1 6 10 9 3 3 5 3 7

输出

复制3 5

3 5

import java.io.*;
import java.util.*;
public class Main{
    public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static Read sc = new Read();
    public  static void  main(String [] args) throws IOException {
        int n= sc.nextInt();
        int x= sc.nextInt();
        //输入数组元素
        int [] array=new int [n+1];
        for(int i=1;i<=n;i++)array[i]=sc.nextInt();
        //start
        int ret=Integer.MAX_VALUE;//最小距离
        int a=-1,b=-1;//保存最后结果
        int left=1,right=1,sum=0;
        while (right<=n&&left<=n){
            if(sum<x)sum+=array[right];
           while (sum>=x){
                 if(right-left+1<ret){
                    a=left;b=right;
                    ret=right-left;
                }
                sum=sum-array[left];
                left++;
            }
            right++;
        }
        System.out.println(a+" "+b);
    }
}
class Read // 自定义快速读入
{
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String next() throws IOException
    {
        while(!st.hasMoreTokens())
        {
            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());
    }
}