[leetcode/lintcode 题解] 阿里巴巴面试真题：数组评分

描述
有一个数组nums，以及三个正整数k,u,l。 对于nums的所有长为k的子段，如果它的总和小于u，就得1分，如果它的总和大于l，就扣1分。 请求出最终能获得多少分？

nums的长度为n，1≤n≤105。 numsi为nums中的元素，0≤numsi≤105。 1≤k≤n。 1≤u≤l≤1010。 最后的得分可以是负数。 下列样例中，[0,1,2,3,4]所有的长为 2 的子段分别是[0,1],[1,2],[2,3],[3,4]，它们的和分别为1,3,5,7。其中 1<2，加一分，7>5，扣一分。总计0分。

在线评测地址：领扣题库官网

样例1
样例输入:
nums = [0, 1, 2, 3, 4]
k = 2
u = 2
l = 5

样例输出:
0

解题思路
如果每次枚举起点，暴力计算求解前 kk 个数的和的话，时间复杂度会达到 O(N2)O(N2)，会超时。所以暴力法不可行。
对于一个长为 kk 的子段，我们可以看作一个长度为 kk 的窗口。对于两个起点相邻的窗口，我们可以在 O(1)O(1) 时间内转移他们的和。如窗口 x,x+k−1 到 x+1,x+k，只需减去第 xx 个值，并加上第 x+kx+k 个值即可。

代码思路

1. 计算前 kk 个数字的和，更新分数。
2. 遍历后 n−kn−k 个数，当遍历到第 ii 个数时，减去第 i−ki−k 个数，更新答案。

复杂度分析
设数组的长度为 NN。
时间复杂度

• 遍历一遍数组，复杂度为 O(N)O(N)。

空间复杂度

• 只需额外 O(1)O(1) 的空间记录分数和子段和。

源代码

public class Solution {
    /**
     * @param nums: the array to be scored.
     * @param k: the requirement of subarray length.
     * @param u: if the sum is less than u, get 1 score.
     * @param l: if the sum is greater than l, lose 1 score.
     * @return: return the sum of scores for every subarray whose length is k.
     */
    public int arrayScore(List<Integer> nums, int k, long u, long l) {
        // 子段的和，这里用long是因为和最大为10^5 * 10^5，用int会溢出
        long sumOfSubarray = 0;
        int score = 0;
        int n = nums.size();
        
        // 先计算前k个的值
        for (int i = 0; i < k; i++) {
            sumOfSubarray += nums.get(i);
        }
        if (sumOfSubarray < u) {
            score++;
        }
        if (sumOfSubarray > l) {
            score--;
        }

        // 剩下的，窗口每次向右移动，加入第 i 个数，弹出第 i - k 个
        for (int i = k; i < n; i++) {
            sumOfSubarray += nums.get(i);
            sumOfSubarray -= nums.get(i - k);
            if (sumOfSubarray < u) {
                score++;
            }
            if (sumOfSubarray > l) {
                score--;
            }
        }
        
        return score;
    }
}

更多题解参考：九章官网solution