滑动窗口经典例题

链接：登录—专业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();//startint 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());}
}