题目描述
给定一个含有N个正整数的数组,求出有多少个连续区间(包括单个正整数),它们的和大于等于x。
输入描述
第一行两个整数 N , x ( 0 < N < = 100000 , 0 < = x < = 10000000 ) N,x\ (0<N<= 100000,0<=x<= 10000000) N,x (0<N<=100000,0<=x<=10000000)
第二行有 N N N个正整数(每个正整数小于等于100)。
输出描述
输出一个整数，表示所求的个数。
注意:此题对效率有要求，暴力解法通过率不高，请考虑 高效的实现方式。
示例1
输入
3 7
3 4 7
输出
4
说明
第一行的3表示第二行数组输入3个数，第一行的7是比较数，用于判断连续数组是否大于该数:组合为3+4;3+4+7;4+7;7; 都大于等于指定的7:所以共四组。
示例2
输入
10 10000
1 2 3 4 5 6 7 8 9 10
输出
0
说明
所有元素的和小于10000，所以返回0。
题解
利用滑动窗口处理,
当滑动窗口的值大于等于给定值的时候，从right边界空时的数组都会大于给定值，连续数组的数量为 length - right + 1
然后移动左边界，重复上述判断
源码
public class ConsectiveArr {static Input input;static {input = new Input("3 7\n" +"3 4 7");input = new Input("10 10000\n" +"1 2 3 4 5 6 7 8 9 10");}public static void main(String[] args) {String[] ss = input.nextLine().split(" ");int length = Integer.parseInt(ss[0]);int sum = Integer.parseInt(ss[1]);String[] arr = input.nextLine().split(" ");int[] intArr = new int[length];int min = Integer.MAX_VALUE;for (int i = 0; i < length; i++) {intArr[i] = Integer.parseInt(arr[i]);min = Math.min(min, intArr[i]);}if (min >= sum) {int count = 0;for (int i = 1; i <= length; i++) {count += i ;}System.out.println(count);return;}int left = 0;int right = 0;int result = 0;int windowSum = intArr[0];while (right < length) {if (windowSum>=sum) {result += length - right + 1;windowSum -= intArr[left];left++;continue;}windowSum += intArr[right];right++;}System.out.println(result);}
}
