题解 | #Subsequence#
技巧:
尺取
思路:
尺取
尺取
实现:
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
int count = Integer.parseInt(br.readLine());
while (count > 0) {
String[] line = br.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int s = Integer.parseInt(line[1]);
String[] arrStr = br.readLine().split(" ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(arrStr[i]);
}
System.out.println(process(n,s,arr));
count--;
}
}
static int process(int n, int s, int[] arr) {
int l = 0;
int r = 1;
int min = (1 << 31) - 1;
if (n == 1 && arr[0] >= s) {
return 1;
}
int sum = arr[l];
while (r < n) {
while (r < n && sum < s) {
sum += arr[r];
r++;
}
if (sum >= s) {
if (r - l < min) {
min = r - l;
}
sum-=arr[l];
l++;
}
}
if (min == (1 << 31) - 1) {
return 0;
}
return min;
}
}
