[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

上一篇:[leetcode/lintcode 题解] 阿里算法面试真题详解:举重


下一篇:如何设计爬虫系统?