[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