前缀和 + 二分
import java.util.Scanner; public class Test7 { int MAX_N = 100005; int[] a = new int[MAX_N]; int[] sum = new int[MAX_N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int s = sc.nextInt(); int ans = new Test7().solve(sc, n, s); System.out.print(ans); } private int solve(Scanner sc, int n, int s) { for (int i = 0; i < n; i++) a[i] = sc.nextInt(); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i - 1]; if (sum[n] < s) return -1; int res = n; for (int i = 0; sum[i] + s <= sum[n]; i++) { int t = binary_search(sum, i, n, s); // System.out.println(t); if (t != n + 1) res = Math.min(res, t - i); } return res; } // a[]: [3, 2, 0] target = 3 // sum[]: [0, 3, 5, 5] // l=0 r=4 mid=2 pre=0 // l=1 r=4 mid=2 pre=3 // [1, 0, 0] // [0, 1, 1, 1] // l=0 r=4 mid=2 pre=0 private int binary_search(int[] sum, int p, int n, int target) { int pre = sum[p]; int l = p, r = n + 1; while (l + 1 < r) { int mid = (l + r) >> 1; if (sum[mid] - pre > target) { r = mid; } else { l = mid; } } if (sum[l] - pre >= target) { return l; } else { return l + 1; } } }滑动窗口
import java.util.Scanner; public class Test7 { int MAX_N = 100005; int[] a = new int[MAX_N]; int[] sum = new int[MAX_N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int s = sc.nextInt(); int ans = new Test7().solve(sc, n, s); System.out.print(ans); } private int solve(Scanner sc, int n, int s) { for (int i = 0; i < n; i++) a[i] = sc.nextInt(); int res = n + 1; int l = 0, r = 0, sum = 0; while (true) { while (r < n && sum < s) { sum += a[r]; r++; } if (sum < s) break; res = Math.min(res, r - l); sum -= a[l]; l++; } if (res == n + 1) { return -1; } else { return res; } } }