2302. Count Subarrays With Score Less Than K
https://leetcode.com/problems/count-subarrays-with-score-less-than-k/
計算符合
陣列元素 * 陣列大小 < K
的子陣列總數
思路：
因為是說子陣列 子陣列=母陣列切片
代表幾乎一定是 Sliding Windows
從 left = 0, right = 0 開始
每輪開始先加上 nums[right]
之後 while 跑 sum * len >= k
慢慢把 nums[left] 蛋雕直到不符合反向條件跳出
之後 count += (right - left + 1)
這邊加的這一串代表以 nums[right] 為一定有的成員
蛋雕後新的 nums[left] 到 nums[right] 每個子陣列
舉例說 left = 0, right = 3
就是 [0~3], [1~3], [2~3], [3~3] 共四個子陣列
所以每次結束都要加 因為每次的 right 都不一樣
最後算完的 count 就是全部的可能性
Code:
impl Solution {
pub fn count_subarrays(nums: Vec<i32>, k: i64) -> i64 {
let mut count: i64 = 0;
let mut sum: i64 = 0;
let mut left = 0;
for right in 0..nums.len() {
sum += nums[right] as i64;
while sum * (right - left + 1) as i64 >= k {
sum -= nums[left] as i64;
left += 1;
}
count += (right - left + 1) as i64;
}
count
}
}