lintcode 1815 · 警报器 【simple vip 前缀和数组】

题目

https://www.lintcode.com/problem/1815

一个烟雾警报器会监测len秒内的烟雾值，如果这段时间烟雾值平均值大于k那么警报器会报警。现在给你n个数代表刚开始工作n秒内警报器监测的烟雾值（警报器从第len秒开始判断是否报警），问警报器在这段时间内会报警几次？1 <= k <= n <= 100000
1 <= len <= 100000
0 <= num[i] <= 100000 (1 <= i <= n)样例
输入: n = 8, k = 4, len = 3, num = [2, 2, 2, 2, 5, 5, 5, 8].
输出: 2
解释: 从 T = 3 to T = 8, 监测的平均值为 2, 2, 3, 4, 5 and 6. 其中5和6 > k, 所以答案shi2.

思考

本答案利用前缀和数组来解答。根据题意：
从第len个开始，求每len个长度的子串平均值是否大于k,大于的话就会报警

参考代码

public class Solution {/*** @param n: * @param k: * @param len: * @param num: same as problem* @return: //return long*/public long solve(int n, int k, int len, int[] num) {//根据题意和例子可知：// 从第len个开始，求每len个长度的子串平均值是否大于k,大于的话就会报警long[] sum = new long[n+1];for (int i = 0; i <n ; i++) {sum[i+1]= sum[i]+ num[i];}int ans =0;for (int i = len; i <=n ; i++) {long cur = (sum[i]-sum[i-len]);if(cur/len >k) ans++;}return ans;}
}