「笔试刷题」：dd爱框框

一、题目

题目描述

读入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

输出

3 5

二、思路解析

这道题是求连续区间的，看到的第一眼，就都要想起 “滑动窗口” 这一算法。

我们可以使用双指针技巧来解决这个问题。具体步骤如下：

初始化两个指针 left 和 right，初始位置都为数组的起始位置。
维护一个变量 sum，表示当前区间内子数组的和。
不断移动 right 指针，将元素加入当前区间，并更新 sum。
当 sum 大于等于 x 时，移动 left 指针，缩小区间范围，并更新 sum，直到区间不再满足 sum 大于等于 x 的条件。
在每次移动 left 和 right 指针时，记录满足条件的区间的最小长度和对应的左右边界。
最终得到的就是满足条件的最小区间。

并且，要注意的一点就是，这道题的数据量会比较大，且传统的 Scanner 读取会耗费比较大的时间，所以我们需要通过重写 IO 流，来提高我们的输入输出效率。

模版我也放在这啦👇

import java.util.*;
import java.io.*;public class Main
{public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static void main(String[] args) throws IOException{// 写代码out.close();}
}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());}
}

三、完整代码

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();int x = in.nextInt();int[] nums = new int[n + 1];for(int i = 1; i <= n; i++){nums[i] = in.nextInt();}int left = 1, right = 1;int sum = 0;int retleft = -1, retright = -1, retLen = n;while(right <= n){sum += nums[right];while(sum >= x){if(right - left + 1 < retLen){retleft = left;retright = right;retLen = right - left + 1;}                sum -= nums[left++];}right++;}System.out.println(retleft + " " + retright);}}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());}
}

以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！