小M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x。
小M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x。
第一行两个整数c x(0 < c <= 1000000, 0 <= x <= 100000000)
第二行有c个正整数(每个正整数小于等于100)。
输出一个整数,表示所求的个数。
3 6 2 4 7
4
对于有3个整数构成的数组而言,总共有6个下标连续的区间,他们的和分别为:
2 = 2
4 = 4
7 = 7
2 + 4 = 6
4 + 7 = 11
2 + 4 + 7 = 13
其中有4个和大于等于6,所以答案等于4。
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int c = sc.nextInt(); int x = sc.nextInt(); int[] arr = new int[c]; for(int i = 0; i < c; i++){ arr[i] = sc.nextInt(); } System.out.println(intervalNums(arr, x)); } private static long intervalNums(int[] arr, int x){ // 这里要用long记录,否则只能a45% long res = 0; int left = 0, right = 0; long sum = arr[left]; while(left < arr.length){ // 符合条件则左指针移动,同时sum减去窗口左端值 if(sum >= x){ res += arr.length - right; sum -= arr[left]; left++; }else{ // 不符合则右指针向右移动扩大窗口,同时sum加上当前窗口右端值 // 当窗口右端到达数组末尾则不能扩大。因为窗口都开到最大还不符合,所以可以直接退出 right++; if(right == arr.length){ break; } sum += arr[right]; } } return res; } }