题目
翻译过来简而言之就是
第1行 输入测试的案例个数
第 i 行 输入N和S (N代表数组长度,S代表目标和)
寻找最短区间满足区间之和大于或者等于S
第 i+1行 输入数组元素
思路
借助快慢指针 i 和 j ,i 在后,j 在前
满足区间之和的话,记录最短区间(j-i+1),刷新区间之和(sum -= a[i],i++ )
不满足区间之和,刷新区间(j++,sum += a[j] )
注意越界问题
尽管大部分测试用例可以通过,还是有一些看不到的奇葩测试,但做蓝桥杯的话,毕竟是按通过测试比例得分,也是值得借鉴的 ~
代码
输入过程都得老半天,恶心啊~ 😠
import java.util.Scanner; //最短连续区间 public class Main{ public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt();//案例的个数 int[] ans = new int[n]; for (int i = 0; i < n; i++) { int size = input.nextInt(); int[] a = new int[size]; int s = input.nextInt(); for (int k = 0; k < size; k++) { int num = input.nextInt(); a[k]=num; } ans[i]=check(a,s); } for (int an : ans) { System.out.println(an); } } public static int check(int[] a,int s){ //快慢指针 int i=0; int j=0; int min=999; int sum=a[0]; while (j<a.length){ int thisMin; if(sum>s){ thisMin=j-i+1; if(thisMin<min){ min=thisMin; } sum-=a[i]; i++; if(i>j){ if(i==a.length){//防止越界 break; } sum=a[i]; j++; } } if(sum==s){ thisMin=j-i+1; if(thisMin<min){ min=thisMin; } sum-=a[i];//找到一个继续找下一个 i++; } if(sum<s){ j++; if(j==a.length){//防止越界 break; } sum+=a[j]; } } return min; } }