題目
一個數組的?分數?定義為數組之和?乘以?數組的長度。
- 比方說，
[1, 2, 3, 4, 5]?的分數為?(1 + 2 + 3 + 4 + 5) * 5 = 75?。
給你一個正整數數組?nums?和一個整數?k?，請你返回?nums?中分數?嚴格小于?k?的?非空整數子數組數目。
子數組?是數組中的一個連續元素序列。
示例 1：
輸入：nums = [2,1,4,3,5], k = 10 輸出：6 解釋： 有 6 個子數組的分數小于 10 ： - [2] 分數為 2 * 1 = 2 。 - [1] 分數為 1 * 1 = 1 。 - [4] 分數為 4 * 1 = 4 。 - [3] 分數為 3 * 1 = 3 。 - [5] 分數為 5 * 1 = 5 。 - [2,1] 分數為 (2 + 1) * 2 = 6 。 注意，子數組 [1,4] 和 [4,3,5] 不符合要求，因為它們的分數分別為 10 和 36，但我們要求子數組的分數嚴格小于 10 。
示例 2：
輸入：nums = [1,1,1], k = 5 輸出：5 解釋： 除了 [1,1,1] 以外每個子數組分數都小于 5 。 [1,1,1] 分數為 (1 + 1 + 1) * 3 = 9 ，大于 5 。 所以總共有 5 個子數組得分小于 5 。
解析
滑動窗口使用前提：
- 連續子數組/子串。
- 有單調性。本題元素均為正數，所以子數組越長，分數越高；子數組越短，分數越低。這意味著只要某個子數組的分數小于 k，在該子數組內的更短的子數組，分數也小于 k。
做法：
- 枚舉子數組的右端點 right，同時維護窗口內的元素和 sum 以及窗口左端點 left。窗口的分數為 sum?(right?left+1)。
- 元素 x=nums[i] 進入窗口，把 sum 增加 x。
- 如果窗口的分數 ≥k，那么把左端點元素 nums[left] 移出窗口，同時減少 sum，把 left 加一。
- 內層循環結束后，[left,right] 這個子數組是合法的。根據上面的使用前提 2，在這個子數組內部的子數組也是合法的，其中右端點小于 right 的子數組，我們在之前的循環中已經統計過了，這里只需要統計右端點恰好等于 right 的合法子數組，即[left,right],[left+1,right],…,[right,right]這一共有 right?left+1 個，加入答案。
作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/solutions/1595722/by-endlesscheng-b120/
來源：力扣（LeetCode）
答案
/*** @param {number[]} nums* @param {number} k* @return {number}*/
var countSubarrays = function(nums, k) {let left = 0, ans = 0, sum = 0; //初始化左指針，子數組個數和子數組的得分for(let right = 0; right < nums.length; right++) { //移動右指針，擴大窗口sum += nums[right]; //更新子數組的和while(sum * (right - left + 1) >= k) { //如果得分大于等于ksum -= nums[left]; //計算減去左端點后的子數組和left++; //移動左指針，縮小窗口}ans += right - left + 1; //更新符合條件的子數組個數}return ans;
};復雜度分析
時間復雜度：O(n)，其中 n 是 nums 的長度。雖然寫了個二重循環，但是內層循環中對 left 加一的總執行次數不會超過 n 次，所以總的時間復雜度為 O(n)。
空間復雜度：O(1)。作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/solutions/1595722/by-endlesscheng-b120/
來源：力扣（LeetCode）
